Dar Birkhoff este mai înţelept: el are nevoie de linişte din partea lui Greg în următoarele ore pentru că are de pregătit o misiune foarte importantă. Ştiind că nu are de gând să rezolve problema propusă de Greg, v-aţi decis să-l ajutaţi pe Birkhoff rezolvând-o pentru el:

Se dau $M$ relaţii despre $N$ vectori *nenuli* în plan, distincţi doi câte doi. O relaţie între vectori spune că înmulţind fiecare dintre cei $N$ vectori cu $-1$, $0$ sau $1$ şi adunând rezultatele se obţine vectorul nul.

Se dau $M$ relaţii despre $N$ vectori *nenuli* în plan, distincţi doi câte doi. O astfel de relaţie între vectori spune că înmulţind fiecare dintre cei $N$ vectori cu $-1$, $0$ sau $1$ şi adunând rezultatele se obţine vectorul nul.

Se mai ştie că pentru fiecare din cele $M$ relaţii există un vector care în relaţia respectivă este înmulţit cu $1$ iar în celelalte $M - 1$ relaţii cu $0$.

Fişierul de intrare $vectori.in$ conţine pe prima linie două numere naturale: $N$ şi $M$.
Pe următoarele $M$ linii se găsesc cele $M$ relaţii, câte una pe linie, codificate astfel: linia unei relaţii conţine $N$ numere ({$-1$}, $0$ sau $1$), reprezentând coeficienţii cu care sunt înmulţiţi cei $N$ vectori.

Pe următoarele $10$ linii se găsesc relaţiile suplimentare, codificare la fel.

Pe următoarele $10$ linii se găsesc relaţiile suplimentare.

h2. Date de ieşire

* $5 ≤ N ≤ 1 000$
* $1 ≤ M ≤ N - 2$

* Coeficienţii care apar în relaţiile suplimentare sunt numere întregi *cuprinse între -1 000 şi 1 000 inclusiv*.

h2. Exemplu

  1 0 1 1 1
  1 0 1 1 1
  1 0 1 1 1

  1 0 1 1 1
| 1 1 1 1 1 0 0 0 0 0

  2 2 0 0 2
| 1 1 1 1 1 0 0 0 0 1

|
h3. Explicaţie
Cele două relaţii date spun că

$v1 + v2 + v5 = 0$
$v3 + v4 - v5 = 0$.

$v{~1~} + v{~2~} + v{~5~} = 0$
$v{~3~} + v{~4~} - v{~5~} = 0$.

Adunându-le, obţinem primele $5$ relaţii suplimentare:

$v1 + v2 + v3 + v4 = 0$.
Ultimele $5$ relaţii suplimentare nu pot fi obţinute din cele date.

$v{~1~} + v{~2~} + v{~3~} + v{~4~} = 0$.
 
Înmulţind prima relaţie cu $2$ obţinem ultima relaţie suplimentară:
$2 * v{~1~} + 2 * v{~2~} + 2 * v{~5~} = 0$
 
Relaţiile suplimentare $6 - 9$ nu pot fi obţinute din cele date.

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