有一个空矩阵 $$$M$$$,大小为 $$$n\times m$$$。
中考结束了,大牛想做一些益智游戏。他将使用长度为 $$$m$$$ 的排列来填充矩阵 $$$M$$$。也就是说,$$$M$$$ 的每一行必须是长度为 $$$m^\dagger$$$ 的排列。
将 $$$M$$$ 中第 $$$i$$$ 列的值定义为 $$$v_i=\operatorname{MEX}(M_{1,i},M_{2,i},\ldots,M_{n,i})^\ddagger$$$。由于 Daniel 喜欢多样性,$$$M$$$ 的美妙之处在于 $$$s=\operatorname{MEX}(v_1,v_2,\cdots,v_m)$$$。
你必须帮助丹尼尔填写矩阵$$$M$$$并最大化它的美丽。
$$$^\dagger$$$ 长度 $$$m$$$ 的排列是一个数组,由从 $$$0$$$ 到 $$$m-1$$$ 的 $$$m$$$ 不同整数组成,顺序任意。例如,$$$[1,2,0,4,3]$$$是一个排列,但$$$[0,1,1]$$$不是排列($$$1$$$在数组中出现两次),$$$[0,1,3]$$$也不是排列($$$m-1=2$$$但数组中有$$$3$$$)。
$$$^\ddagger$$$ 数组的 $$$\operatorname{MEX}$$$ 是不属于该数组的最小非负整数。例如, $$$\operatorname{MEX}(2,2,1)=0$$$ 因为 $$$0$$$ 不属于数组,而 $$$\operatorname{MEX}(0,3,1,2)=4$$$ 因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 出现在数组中,但 $$$4$$$ 没有出现在数组中。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\let t\le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n,m\le 2\cdot 10^5$$$) — 矩阵的大小。
保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在第一行输出一个整数 - $$$M$$$ 的最大美感。
然后输出大小为 $$$n\times m$$$ 的矩阵 $$$M$$$ — 您找到的矩阵。
如果有多个解,则可以输出其中任何一个。
示例
输入 #1
4 4 3 1 16 6 6 2 1
输出 #1
3 1 0 2 0 2 1 1 0 2 0 2 1 2 14 7 15 4 10 0 8 6 1 2 3 5 9 11 12 13 6 3 0 1 4 2 5 5 2 1 0 4 3 1 3 2 4 5 0 4 1 3 2 5 0 4 2 5 3 0 1 2 4 0 5 1 3 0 0 0
注意
在第一个测试用例中:
- $$$v_1=\operatorname{MEX}(1,0,1,0)=2$$$;
- $$$v_2=\operatorname{MEX}(0,2,0,2)=1$$$;
- $$$v_3=\operatorname{MEX}(2,1,2,1)=0$$$。
因此,$$$s=\operatorname{MEX}(2,1,0)=3$$$。
可以证明$$$3$$$是$$$M$$$的最大可能美度。
在第二个测试用例中,任何排列都会使$$$s=2$$$。
在第三个测试用例中:
- $$$v_1=\operatorname{MEX}(3,5,1,4,4,2)=0$$$;
- $$$v_2=\operatorname{MEX}(0,2,3,1,2,4)=5$$$;
- $$$v_3=\operatorname{MEX}(1,1,2,3,5,0)=4$$$;
- $$$v_4=\operatorname{MEX}(4,0,4,2,3,5)=1$$$;
- $$$v_5=\operatorname{MEX}(2,4,5,5,0,1)=3$$$;
- $$$v_6=\operatorname{MEX}(5,3,0,0,1,3)=2$$$。
因此,$$$s=\operatorname{MEX}(0,5,4,1,3,2)=6$$$。