题目描述

Mutu 正在学习 C++。老师要求他写一个有 $N$ 个整型参数的函数：

$$f : \{0,1,\ldots,10^6\}^{N} \to \{0,1,\ldots,10^6\}.$$

同时，老师给出了 $M$ 条约束，这些约束用一个大小为 $M\times (N+1)$ 的矩阵 $A$ 表示。矩阵行编号为 $1\sim M$，列编号为 $1\sim N+1$。第 $i$ 条约束要求：

$$f(A_{i,1},A_{i,2},\ldots,A_{i,N})=A_{i,N+1}.$$

但是 Mutu 会写的程序结构很有限。你需要帮他写出的函数只能是下面这种形式：

int f(int x1, ..., int xN) {
    if (x_i1 == j1) return k1;
    if (x_i2 == j2) return k2;
    ...
    if (x_iL == jL) return kL;
    return -1;
}

你可以自行选择判断语句的数量 $L$，以及每条语句中的三元组：

$$(i_1,j_1,k_1),(i_2,j_2,k_2),\ldots,(i_L,j_L,k_L).$$

函数会按顺序执行这些 if。也就是说，对于某个输入向量，函数会返回第一条满足条件的语句对应的 $k_t$；如果没有任何语句满足，则返回 -1。

任务

给定 $N,M$ 和矩阵 $A$，请构造一组 if 语句，使得上述函数满足所有 $M$ 条约束。

如果不存在这样的函数，输出 -1。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含 $N+1$ 个整数，第 $i$ 行第 $j$ 个数表示 $A_{i,j}$。

输出格式

如果无解，输出一行：

-1

否则输出 $L$ 行，每行三个整数：

i_x j_x k_x

第 $x$ 行表示一条语句：

if (x_i_x == j_x) return k_x;

输出的语句顺序就是函数中判断语句的执行顺序。

数据范围

• $1\le N\cdot M\le 1\,000\,000$；
• $0\le A_{i,j}\le 1\,000\,000$，其中 $1\le i\le M$，$1\le j\le N+1$；
• 对于输出的每条三元组，应满足 $1\le i_x\le N$，$0\le j_x,k_x\le 1\,000\,000$；
• $1\le L\le 2\,000\,000$。

题目保证：如果存在解，则存在一个三元组数量不超过 $2\,000\,000$ 的解。

子任务

子任务	分值	限制
1	11	$N\cdot M\le 50$
2	23	$N\cdot M\le 200\,000$
3	18	$N\cdot M\le 500\,000$
4	48	无额外限制

注：第 4 个子任务包含两个测试组，分值分别为 29 和 19。

样例 1

输入

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

输出

4 9 0
2 2 4
1 3 2

样例 1 解释

输出对应的函数为：

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;
}

它满足：

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

样例 2

输入

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

输出

-1