这是一场编程竞赛吗？

给定一个素数 $p$ 和一个 $n \times n$ 的非零对称矩阵 $G$，其中每个元素都是 $[0, p)$ 范围内的整数。 Little Cyan Fish 请你找到满足以下条件的最小整数 $m$：

• 存在 $n$ 个长度为 $m$ 的数组 $v_1, \dots, v_n$，其中每个元素都是 $[0, p)$ 范围内的整数，使得对于所有 $1 \le i, j \le n$，满足： $$G_{i,j} = \left( \sum_{k=1}^{m} v_{i,k} v_{j,k} \right) \pmod p$$

输入格式

第一行包含两个整数 $n$ 和 $p$ ($1 \le n \le 500, 2 \le p \le 10^6$)。 接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个整数为 $G_{i,j}$ ($0 \le G_{i,j} < p$, $G_{i,j} = G_{j,i}$ 对于所有 $1 \le i, j \le n$ 成立，$G \neq 0$)。 保证 $p$ 是一个素数，且至少存在一个可行解。

输出格式

第一行输出一个整数 $m$，表示最小可能的整数 $m$。 接下来的 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行的第 $j$ 个整数为 $v_{i,j}$。 如果存在多个可行解，你可以输出其中任意一个。

样例

样例输入 1

2 2
1 1
1 1

样例输出 1

1
1
1

样例输入 2

3 5
4 4 3
4 4 3
3 3 2

样例输出 2

2
3 0
3 0
1 4