魔法少女 Nene 有一个用零填充的 $$$n\times n$$$ 矩阵 $$$a$$$。矩阵$$$a$$$第$$$i$$$行的第$$$j$$$元素表示为$$$a_{i, j}$$$。
她可以用这个矩阵执行以下两种类型的运算:
- 输入 $$$1$$$ 操作:选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$ 以及从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$。同时为所有 $$$1 \le j \le n$$$ 分配 $$$a_{i, j}:=p_j$$$。
- 输入 $$$2$$$ 操作:选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$ 以及从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$。同时为所有 $$$1 \le j \le n$$$ 分配 $$$a_{j, i}:=p_j$$$。
Nene 想要最大化矩阵 $$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$$$ 中所有数字的总和。她要求你找到执行运算的方法,以使这个总和最大化。由于她不想进行太多操作,因此您应该提供一个不超过 $$$2n$$$ 操作的解决方案。
长度 $$$n$$$ 的排列是一个由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 矩阵 $$$a$$$ 的大小。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,在第一行输出两个整数 $$$s$$$ 和 $$$m$$$ ($$$0\leq m\leq 2n$$$) - 矩阵中的数字与解决方案中的操作数的最大总和。
在接下来的 $$$m$$$ 行的第 $$$k$$$ 行中输出第 $$$k$$$ 操作的描述:
- 整数 $$$c$$$ ($$$c \in \{1, 2\}$$$) — 第 $$$k$$$ 操作的类型;
- 整数 $$$i$$$ ($$$1 \le i \le n$$$) - 第 $$$k$$$ 操作应用到的行或列;
- 从 $$$1$$$ 到 $$$n$$$ 的整数的排列 $$$p_1, p_2, \ldots, p_n$$$ - 第 $$$k$$$ 操作中使用的排列。
请注意,您不需要最小化所使用的操作数量,您只应该使用不超过 $$$2n$$$ 操作。可以证明,总是可以在不超过 $$$2n$$$ 操作中获得最大可能的总和。
示例
输入 #1
2 1 2
输出 #1
1 1 1 1 1 7 3 1 1 1 2 1 2 1 2 2 1 1 2
注意
在第一个测试用例中,通过设置$$$a_{1, 1}:=1$$$,可以在$$$1$$$操作中获得最大和$$$s=1$$$。
在第二个测试用例中,可以通过$$$3$$$操作获得最大和$$$s=7$$$,如下所示:
可以证明,不可能使矩阵中的数字之和大于$$$7$$$。