dictator

Dictator

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.

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

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

| $4$ | $20$ | $N, M, Q ≤ 50$ |
| $5$ | $30$ | Fără alte restricţii |

h2. Exemplul 1

h2. Exemple

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

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:

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 (în fiecare celulă, $A{~i~} + B{~j~}$):

$$
\begin{pmatrix}
0 + 5 & 0 + 5 \\
2 + 5 & 2 + 5
\end{pmatrix}
=
\begin{pmatrix}
5 & 5 \\
7 & 7
\end{pmatrix}
$$

table. |_. |_. $B{~1~}=5$ |_. $B{~2~}=5$ |
|_. $A{~1~}=0$ | $0+5=5$ | $0+5=5$ |
|_. $A{~2~}=2$ | $2+5=7$ | $2+5=7$ |

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

* *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. Exemplul 2
 

table(example). |_. dictator.in |_. dictator.out |
| 1 1 2
0 1 1 1 1 10