Dictator

Allison Burgers, activist recunoscut la nivel mondial are o armată de $N \cdot M$ oameni așezați într-o matrice cu $N$ linii și $M$ coloane. Se știe ca 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ăsura, 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ățiile de aladeen din submatricea respectivă să fie $\geq k$, $\leq k$ sau $= k$, în funcție de tipul restricției.

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.

Date de intrare

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$.

Date de ieșire

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, \dots, A_N$), iar pe a doua linie se vor afișa $M$ numere întregi reprezentând elementele vectorului $B$ ($B_1, B_2, \dots, B_M$). Numerele de pe fiecare linie vor fi separate prin câte un spațiu.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000$
• $1 \leq Q \leq 1 \ 000$
• $-1 \ 000 \leq k \leq 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 \leq x_1 \leq x_2 \leq N$ și $1 \leq y_1 \leq y_2 \leq M$.

Exemplul 1

dictator.in

2 2 3
2 1 1 1 2 5
0 2 1 2 1 6
1 2 2 2 2 8

dictator.out

0 2
5 5

Explicație

vem $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:

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 $\geq 6$. Valoarea este $7$, iar $7 \geq 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 $\leq 8$. Valoarea este $7$, iar $7 \leq 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]$.

Exemplul 2

dictator.in

1 1 2
0 1 1 1 1 10
1 1 1 1 1 5

dictator.out

-1

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 $\geq 10$, iar a doua restricție impune ca acesta să fie $\leq 5$. Este imposibil ca un număr să respecte simultan ambele condiții, prin urmare răspunsul este $-1$.