题目描述
食堂的桌子可以被视作 $n\times n$ 的矩阵。建造食堂的任务还剩下给桌子分配标号。
你需要将 $1\sim n^2$ 的所有整数分配给食堂的每个桌子，可能有 $k(k\le2)$ 个桌子已经被分配了标号。
定义食堂的规范度为每行每列桌子标号极差的最小值，你需要最大化食堂的规范度，构造方案。
本题有多组数据。
输入格式
第一行一个正整数 $T$ 表示数据组数。
对于每组数据，第一行两个整数 $n,k$，接下来 $k$ 行每行三个正整数 $x_i,y_i,w_i$，表示食堂第 $x_i$ 行 $y_i$ 列的桌子标号为 $w_i$。
输出格式
对于每组数据，第一行输出一个正整数表示最大的规范度。
之后 $n$ 行，每行输出 $n$ 个数，第 $i$ 行第 $j$ 个数表示第 $i$ 行 $j$ 列桌子的标号。多解输出任意一组。
样例
样例1输入
3
2 0
2 2
1 1 4
1 2 3
3 1
1 2 3样例1输出
1
1 2
3 4
1
4 3
1 2
5
4 3 8
1 9 5
7 6 2数据范围
保证 $1\le T\le10,1\le n\le1000,\sum n^2\le10^6,0\le k\le2,1\le x_i,y_i\le n,1\le w_i\le n^2$，对于任意 $1\le i
| 测试点编号 | $n\le$ | $k=$ | 特殊性质 |
|---|---|---|---|
| $1$ | $2$ | $2$ | 无 |
| $2$ | $3$ | $2$ | 无 |
| $3$ | $5$ | $2$ | 无 |
| $4$ | $10$ | $2$ | 无 |
| $5\sim6$ | $100$ | $2$ | 无 |
| $7\sim9$ | $1000$ | $0$ | 无 |
| $10$ | $1000$ | $1$ | 无 |
| $11\sim12$ | $1000$ | $2$ | $w_1\in[1,\frac{2n^2}{3}],w_2\in[\frac{n^2}{3},\frac{2n^2}{3}]$ |
| $13\sim14$ | $1000$ | $2$ | $w_i\in[1,\frac{n^2}{3}]$ |
| $15\sim16$ | $1000$ | $2$ | $x_1\not=x_2,y_1\not=y_2$ |
| $17\sim20$ | $1000$ | $2$ | 无 |