Graba

Mutu studiază limbajul C++ și tocmai a învățat despre funcții și instrucțiunea "if". Pentru a îi testa noile îndeletniciri, Surdu, profesorul său, i-a dat temă să scrie o funcție $f$ cu $N$ argumente de tip întreg $x_1, \ldots, x_N$ care returnează un întreg. Pentru a îi îngreuna misiunea, tema include $M$ constrângeri suplimentare pe care funcția $f$ trebuie să le satisfacă, specificate printr-o matrice de dimensiuni $M × (N + 1)$, notată cu $A$, ale cărei linii și coloane sunt numerotate de la $1$ la $M$ și respectiv de la $1$ la $N + 1$. Cea de-a $i$-a constrângere pentru $1 \leq i \leq M$ este că $f(A_{i,1}, \ldots, A_{i,N}) = A_{i,N + 1}$ . Deoarece Mutu se grăbește să se califice în lotul național de informatică, el vă roagă pe voi să îi faceți tema: adică să scrieți funcția $f$ pentru el.

Deoarece cunoștințele lui Mutu sunt încă limitate, funcția $f$ trebuie să se încadreze în materia predată, altminteri Surdu își va da seama de tentativa de fraudă. Așadar, funcția $f$ trebuie să respecte următorul format, din care Mutu nu poate alege decât numărul $l$ și tripletele $(i_1, j_1, k_1)$, $(i_2, j_2, k_2)$, $\ldots$, $(i_l, j_l, k_l)$:

int f(int x1, ..., int xN) {
    if (xi1 == j1) return k1;
    if (xi2 == j2) return k2;
    ...
    if (xil == jl) return kl;
    return -1;
}

Cerință

Date fiind $N$, $M$ și matricea $A$ determinați $l$ și $l$ triplete $(i_1, j_1, k_1)$, $\ldots$, $(i_l, j_l, k_l)$ astfel încât funcția $f$ definită mai sus să satisfacă cele $M$ constrângeri. În cazul în care nu există nicio soluție, precizați acest lucru.

Date de intrare

Pe prima linie a fișierului de intrare graba.in se află $N$ și $M$. Următoarele $M$ linii conțin câte $N + 1$ numere întregi, al $j$-lea număr de pe a $i$-a dintre aceste linii reprezentând elementul $A_{i,j}$ al matricei.

Date de ieșire

Dacă nu există nicio soluție, fișierul de ieșire graba.out va conține o singură linie cu -1. Altfel, fișierul de ieșire va conține $l$ linii, dintre care a $x$-a linie pentru $1 \leq x \leq l$ va conține numerele $i_x, j_x, k_x$, separate prin spații.

Restricții și precizări

• $1 \leq N \cdot M \leq 1 \ 000 \ 000$
• $0 \leq A_{i,j} \leq 1 \ 000 \ 000$ pentru $1 \leq i \leq M$ și $1 \leq j \leq N + 1$
• $1 \leq i_x \leq N$ pentru $1 \leq x \leq l$
• $0 \leq j_x, k_x \leq 1 \ 000 \ 000$ pentru $1 \leq x \leq l$
• $1 \leq l \leq 2 \ 000 \ 000$. Se garantează că în cazul în care există soluție, aceasta se poate obține cu cel mult $2\ 000\ 000$ de triplete.

Notă: Subtaskul 4 conține două grupe de teste, în valoare de $29$ și respectiv $19$ puncte

Exemplul 1

graba.in

4 3
3 2 3 4 4
8 2 2 5 4
3 3 3 6 2

graba.out

4 9 0
2 2 4
1 3 2

Explicație

Mutu alege $l = 3$ triplete $(4, 9, 0)$, $(2, 2, 4)$ și $(1, 3, 2)$, ducând la următoarea funcție $f$ cu $N = 4$ argumente:

int f(int x1, int x2, int x3, int x4) {
	if (x4 == 9) return 0;
	if (x2 == 2) return 4;
	if (x1 == 3) return 2;
	return -1;
}

Această funcție respectă cele $M = 3$ constrângeri date:

• $f(3, 2, 3, 4) = 4$
• $f(8, 2, 2, 5) = 4$
• $f(3, 3, 3, 6) = 2$

Exemplul 2

graba.in

2 4
0 0 0
0 1 1
1 0 1
1 1 0

graba.out

-1

Explicație

Nicio funcție $f$ de forma dată nu respectă cele $M = 4$ constrângeri date.