== include(page="template/taskheader" task_id="dictator") ==

Poveste şi cerinţă...

Allison Burgers, activist recunoscut la nivel mondial, are o armată de $N · M$ oameni aşezaţi într-o matrice cu $N$ linii şi $M$ coloane. Se ştie că fiecare om de pe linia $i$ are $A{~i~}$ unităţi de _aladeen_, iar fiecare om de pe coloana $i$ are $B{~i~}$ unităţi de _aladeen_. Deşi teoretic _aladeen_ şi _aladeen_ sunt două unităţi diferite de măsură, ignorăm acest lucru şi tragem concluzia că omul aflat pe linia $i$ şi coloana $j$ are în total $A{~i~} + B{~j~}$ unităţi de _aladeen_.
 
Deoarece Allison Burgers este o persoană foarte open-minded, el impune $Q$ restricţii. O restricţie este definită prin coordonatele $(x{~1~}, y{~1~})$ şi $(x{~2~}, y{~2~})$ ale colţurilor stânga-sus, respectiv dreapta-jos ale unei submatrici, alături de o valoare întreagă $k$. Aceasta impune ca toate unităţile de _aladeen_ din submatricea respectivă să fie $≥ k$, $≤ k$ sau $= k$, în funcţie de tipul restricţiei.
 
h2. Cerinţă
 
Cunoscând cele $Q$ restricţii, să se determine elementele celor doi vectori $A$ şi $B$ cu valori cuprinse în intervalul $[-10^9^, 10^9^]$ care respectă toate condiţiile date. Dacă există mai multe perechi de vectori care generează o matrice validă, se pot afişa oricare dintre ele. Dacă nu există nicio soluţie, se va afişa $-1$. Nu vreţi să aflaţi ce se întâmplă dacă nu sunt respectate restricţiile.

h2. Date de intrare

Fişierul de intrare $dictator.in$ ...

Fişierul de intrare $dictator.in$ conţine pe prima linie trei numere naturale $N$, $M$ şi $Q$, separate prin câte un spaţiu. Pe următoarele $Q$ linii sunt descrise restricţiile. Fiecare linie va conţine şase numere întregi, separate prin câte un spaţiu: $type$, $x{~1~}$, $y{~1~}$, $x{~2~}$, $y{~2~}$ şi $k$, unde:
 
* $type = 0$ înseamnă că toate valorile din submatrice trebuie să fie *mai mari sau egale* decât $k$.
* $type = 1$ înseamnă că toate valorile din submatrice trebuie să fie *mai mici sau egale* decât $k$.
* $type = 2$ înseamnă că toate valorile din submatrice trebuie să fie *egale* cu $k$.

h2. Date de ieşire

În fişierul de ieşire $dictator.out$ ...

Fişierul de ieşire $dictator.out$ va conţine:
 
* Valoarea $-1$ pe o singură linie, dacă nu se poate construi o astfel de matrice.
* Dacă există cel puţin o soluţie validă, pe prima linie se vor afişa $N$ numere întregi reprezentând elementele vectorului $A$ ($A{~1~}, A{~2~}, …, A{~N~}$), iar pe a doua linie se vor afişa $M$ numere întregi reprezentând elementele vectorului $B$ ($B{~1~}, B{~2~}, …, B{~M~}$). Numerele de pe fiecare linie vor fi separate prin câte un spaţiu.
 
h2. Restricţii şi precizări
 
* $1 ≤ N, M ≤ 1\ 000$
* $1 ≤ Q ≤ 1\ 000$
* $-1\ 000 ≤ k ≤ 1\ 000$
* Valorile afişate pentru elementele vectorilor $A$ şi $B$ trebuie să se afle în intervalul $[-10^9^, 10^9^]$.
* Pentru fiecare restricţie, se garantează că $1 ≤ x{~1~} ≤ x{~2~} ≤ N$ şi $1 ≤ y{~1~} ≤ y{~2~} ≤ M$.
 
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $10$ | $N = 1$ |
| $2$ | $15$ | $N, M, Q ≤ 100$ şi toate restricţiile au $type = 2$ |
| $3$ | $25$ | Toate restricţiile au $type = 2$ |
| $4$ | $20$ | $N, M, Q ≤ 50$ |
| $5$ | $30$ | Fără alte restricţii |
 
h2. Exemplul 1
 
table(example). |_. dictator.in |_. dictator.out |
| 2 2 3
2 1 1 1 2 5
0 2 1 2 1 6
1 2 2 2 2 8
| 0 2
5 5
|
 
h3. Explicaţie
 
Avem $N=2$ linii, $M=2$ coloane şi $Q=3$ restricţii. Vectorii găsiţi sunt $A = [0, 2]$ şi $B = [5, 5]$. Matricea generată folosind formula $A{~i~} + B{~j~}$ va arăta astfel:

h2. Restricţii

$$
\begin{pmatrix}
0 + 5 & 0 + 5 \\
2 + 5 & 2 + 5
\end{pmatrix}
=
\begin{pmatrix}
5 & 5 \\
7 & 7
\end{pmatrix}
$$
 
Să verificăm dacă matricea generată respectă cele $3$ restricţii:
 
* *Restricţia 1* ($type=2, x{~1~}=1, y{~1~}=1, x{~2~}=1, y{~2~}=2, k=5$): Elementele de pe linia $1$, coloanele de la $1$ la $2$ trebuie să fie $== 5$. Elementele sunt $5$ şi $5$, deci condiţia este respectată.
* *Restricţia 2* ($type=0, x{~1~}=2, y{~1~}=1, x{~2~}=2, y{~2~}=1, k=6$): Elementul de pe linia $2$, coloana $1$ trebuie să fie $≥ 6$. Valoarea este $7$, iar $7 ≥ 6$, deci condiţia este respectată.
* *Restricţia 3* ($type=1, x{~1~}=2, y{~1~}=2, x{~2~}=2, y{~2~}=2, k=8$): Elementul de pe linia $2$, coloana $2$ trebuie să fie $≤ 8$. Valoarea este $7$, iar $7 ≤ 8$, deci condiţia este respectată.

* $... ≤ ... ≤ ...$

Aceasta nu este singura soluţie validă. O altă soluţie acceptată ar putea fi, de exemplu, $A = [2, 4]$ şi $B = [3, 3]$.

h2. Exemplu

h2. Exemplul 2

table(example). |_. dictator.in |_. dictator.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 1 1 2
0 1 1 1 1 10
1 1 1 1 1 5
| -1
|

h3. Explicaţie

...

Trebuie să construim o matrice cu o linie şi o coloană ($N=1$, $M=1$). Prima restricţie impune ca unicul element să fie $≥ 10$, iar a doua restricţie impune ca acesta să fie $≤ 5$. Este imposibil ca un număr să respecte simultan ambele condiţii, prin urmare răspunsul este $-1$.

== include(page="template/taskfooter" task_id="dictator") ==
 

== include(page="template/taskfooter" task_id="dictator") ==