给定一个素数 $p$，我们将一个大小为 $n \times n$、元素取值范围在 $0$ 到 $p-1$（包含边界）之间的数组称为矩阵。矩阵 $M$ 第 $i$ 行第 $j$ 列（$1 \le i, j \le n$）的元素记作 $M_{i,j}$。由于我们不知道除了 $10^9 + 7$ 以外的其他大素数，我们现在假设 $p = 1\,000\,000\,007$。

如果矩阵 $A$ 和矩阵 $B$ 满足以下条件，则称 $B$ 为 $A$ 的逆矩阵：对于任意 $1 \le i, j \le n$，求和 $$\sum_{\ell=1}^{n} A_{i,\ell} \cdot B_{\ell,j}$$ 除以 $p$ 的余数在 $i = j$ 时为 $1$，否则为 $0$。

给定矩阵 $A$。我们保证存在唯一的矩阵 $B$ 是 $A$ 的逆矩阵。你的任务是找到矩阵 $B$。

为了简化问题，我们还提供了矩阵 $C$，它与所求矩阵 $B$ 最多有十二个元素不同。你的任务是输出矩阵 $C$ 与目标矩阵 $B$ 不同的元素列表。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示矩阵 $A$ 的维度。

接下来的 $n$ 行描述矩阵 $A$；其中第 $i$ 行包含 $n$ 个整数，第 $j$ 个数字为元素 $A_{i,j}$ ($0 \le A_{i,j} \le p - 1$)。我们保证存在唯一的矩阵 $B$ 是 $A$ 的逆矩阵。

随后的 $n$ 行以类似的格式描述矩阵 $C$。你可以假设矩阵 $C$ 与矩阵 $B$ 最多有十二个元素不同。具体来说，最多存在十二个不同的自然数对 $(i, j)$，满足 $1 \le i, j \le n$ 且 $B_{i,j} \neq C_{i,j}$。

输出格式

输出的第一行应包含一个整数 $k$ ($0 \le k \le 12$)，表示矩阵 $C$ 中需要修改以得到矩阵 $B$ 的元素个数。

接下来的 $k$ 行，每行包含三个整数。第 $i$ 行的数字依次为 $x_i, y_i$ 和 $w_i$ ($1 \le x_i, y_i \le n, 0 \le w_i \le p - 1$)，表示在目标矩阵 $B$ 中，$B_{x_i,y_i} = w_i$，而 $C_{x_i,y_i} \neq w_i$。修改后的元素应按行号升序排列，若行号相同，则按列号升序排列。

注意，根据题目条件，正确的输出是唯一确定的。

样例

样例输入 1

2
1 1
0 2
1 2
3 500000004

样例输出 1

2
1 2 500000003
2 1 0

样例输入 2

3
0 1 0
0 0 1
1 0 0
0 0 1
1 0 0
0 1 0

样例输出 2

0

说明

矩阵 $A = \begin{bmatrix} 1 & 1 \\ 0 & 2 \end{bmatrix}$ 的逆矩阵为 $B = \begin{bmatrix} 1 & 500\,000\,003 \\ 0 & 500\,000\,004 \end{bmatrix}$。因此，输入中提供的矩阵 $C$ 有两个元素需要修改。