#P18553. Nightmare

Nightmare

Nightmare

这真的是一场程序设计竞赛吗?

给定一个素数 pp,以及一个 n×nn\times n 的非零对称矩阵 GG。矩阵的每个元素都是 [0,p)[0,p) 内的整数。

Little Cyan Fish 请你找到满足以下条件的最小整数 mm:存在 nn 个长度为 mm 的数组 v1,…,vnv_1,\ldots,v_n,其中每个元素都是 [0,p)[0,p) 内的整数,且对于所有 1≤i,j≤n1\le i,j\le n,都有

$$G_{i,j}=\left(\sum_{k=1}^{m}v_{i,k}v_{j,k}\right)\bmod p.$$

你需要输出最小的 mm,以及一组满足上述要求的数组。

输入格式

第一行包含两个整数 n,pn,p(1≤n≤5001\le n\le500,2≤p≤1062\le p\le10^6)。

随后 nn 行,每行包含 nn 个整数。第 ii 行的第 jj 个整数是 Gi,jG_{i,j}(0≤Gi,j<p0\le G_{i,j}<p)。

保证对所有 1≤i,j≤n1\le i,j\le n 都有 Gi,j=Gj,iG_{i,j}=G_{j,i},且 G≠0G\ne0。

保证 pp 是素数,并且至少存在一组可行解。

输出格式

第一行输出一个整数 mm,表示满足要求的最小长度。

随后 nn 行,每行输出 mm 个整数。第 ii 行的第 jj 个整数是 vi,jv_{i,j},必须属于 [0,p)[0,p)。

如果存在多组最优解,可以输出任意一组。

原样例 1

2 2
1 1
1 1
1
1
1

原样例 2

3 5
4 4 3
4 4 3
3 3 2
2
3 0
3 0
1 4