Kirill 想要编织一条非常漂亮的毯子,它由 $$$n \times m$$$ 相同大小的某些颜色的方形块组成。他将一些非负整数与每种颜色相匹配。因此,在我们的问题中,毯子可以被视为由非负整数组成的大小为 $$$n \times m$$$ 的 $$$B$$$ 矩阵。
基里尔认为毯子非常漂亮,如果对于矩阵 $$$B$$$ 大小为 $$$4 \times 4$$$ 的每个子矩阵 $$$A$$$ 为真:
- $$$A_{11} \oplus A_{12} \oplus A_{21} \oplus A_{22} = A_{33} \oplus A_{34} \oplus A_{43} \oplus A_{44},$$$
- $$$A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42},$$$
其中 $$$\oplus$$$ 表示按位异或
基里尔要求你帮她编织一条非常漂亮的毯子,并且尽可能丰富多彩!
他给了你两个整数 $$$n$$$ 和 $$$m$$$。
你的任务是生成一个大小为 $$$n \times m$$$ 的矩阵 $$$B$$$,它对应于一条非常漂亮的毯子,并且其中不同数字的数量最大化。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的单行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(4 \le n, \, m \le 200)$$$ — 矩阵 $$$B$$$ 的大小。
保证$$$n \cdot m$$$ 之和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在第一行输出一个整数 $$$cnt$$$ $$$(1 \le cnt \le n \cdot m)$$$ — 矩阵中不同数字的最大数量。
然后输出大小为$$$n \times m$$$的矩阵$$$B$$$ $$$(0 \le B_{ij} < 2^{63})$$$。如果有多个正确矩阵,则允许输出任意一个。
可以证明,如果存在一个具有最优个数的不同数字的矩阵,则在合适的矩阵中存在$$$B$$$ $$$(0 \le B_{ij} < 2^{63})$$$。
示例
输入 #1
4 5 5 4 4 4 6 6 6
输出 #1
25 9740 1549 9744 1553 9748 1550 1551 1554 1555 1558 10252 2061 10256 2065 10260 2062 2063 2066 2067 2070 10764 2573 10768 2577 10772 16 3108 3109 3112 3113 3110 3111 3114 3115 3620 3621 3624 3625 3622 3623 3626 3627 24 548 549 552 553 556 557 550 551 554 555 558 559 1060 1061 1064 1065 1068 1069 1062 1063 1066 1067 1070 1071 36 25800 25801 25804 25805 25808 25809 25802 4294993099 25806 4294993103 25810 4294993107 26312 26313 26316 26317 26320 26321 26314 4294993611 26318 4294993615 26322 4294993619 26824 26825 26828 26829 26832 26833 26826 4294994123 26830 4294994127 26834 4294994131
注意
在第一个测试用例中,只有 4 个大小为 $$$4 \times 4$$$ 的子矩阵。考虑一个子矩阵,其左上角与矩阵 $$$B$$$ 的左上角重合:
$$$ \left[ {\begin{array}{cccc} 9740 & 1549 & 9744 & 1553 \\ 1550 & 1551 & 1554 & 1555 \\ 10252 & 2061 & 10256 & 2065 \\ 2062 & 2063 & 2066 & 2067 \\ \end{数组} } \right] $$$
$$$9740 \oplus 1549 \oplus 1550 \oplus 1551$$$ $$$=$$$ $$$10256 \oplus 2065 \oplus 2066 \oplus 2067$$$ $$$=$$$ $$$8192$$$;
$$$10252 \oplus 2061 \oplus 2062 \oplus 2063$$$ $$$=$$$ $$$9744 \oplus 1553 \oplus 1554 \oplus 1555$$$ $$$=$$$ $$$8192$$$。
因此,所选子矩阵符合条件。同样,您可以确保其他三个子矩阵也符合条件。