给定两个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。保证从 $$$1$$$ 到 $$$2 \cdot n$$$ 的每个整数恰好出现在其中一个数组中。
您需要执行一定数量的操作(可能为零),以便 两者 满足以下条件的 :
- 对于每个 $$$1 \leq i \lt n$$$,它认为 $$$a_i \lt a_{i + 1}$$$ 和 $$$b_i \lt b_{i + 1}$$$。
- 对于每个 $$$1 \leq i \leq n$$$,它认为 $$$a_i \lt b_i$$$。
在每个操作期间,您可以执行以下三个操作之一:
- 选择索引 $$$1 \leq i \lt n$$$ 并交换值 $$$a_i$$$ 和 $$$a_{i + 1}$$$。
- 选择索引 $$$1 \leq i \lt n$$$ 并交换值 $$$b_i$$$ 和 $$$b_{i + 1}$$$。
- 选择索引 $$$1 \leq i \leq n$$$ 并交换值 $$$a_i$$$ 和 $$$b_i$$$。
您不需要最小化操作次数,但总数不得超过$$$1709$$$。找到满足以下条件的任意操作序列 两者 满足以下条件的 条件。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 40$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot n$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 2 \cdot n$$$)。
保证从 $$$1$$$ 到 $$$2 \cdot n$$$ 的每个整数出现在数组 $$$a$$$ 或数组 $$$b$$$ 中。
输出
对于每个测试用例,输出操作序列。
在每个测试用例的第一行,输出操作数$$$k$$$。请注意 $$$0 \leq k \leq 1709$$$。
在每个测试用例的以下 $$$k$$$ 行中,输出操作本身:
- 如果要交换 $$$a_i$$$ 和 $$$a_{i + 1}$$$ 的值,请输出两个整数 $$$1$$$ 和 $$$i$$$。请注意 $$$1 \leq i \lt n$$$。
- 如果要交换 $$$b_i$$$ 和 $$$b_{i + 1}$$$ 的值,请输出两个整数 $$$2$$$ 和 $$$i$$$。请注意 $$$1 \leq i \lt n$$$。
- 如果要交换值 $$$a_i$$$ 和 $$$b_i$$$,请输出两个整数 $$$3$$$ 和 $$$i$$$。请注意 $$$1 \leq i \leq n$$$。
可以证明,在给定的约束下,解总是存在。
示例
输入复制
611212121 34 221 43 236 5 43 2 135 3 42 6 1
输出复制
0 1 3 1 1 2 1 1 3 2 9 3 1 3 2 3 3 1 1 2 1 2 2 1 2 1 1 2 1 6 2 2 1 1 1 2 2 1 3 1 3 2
注意
在第一个测试用例中,$$$a_1 \lt b_1$$$,因此不需要应用任何操作。
在第二个测试用例中,$$$a_1 \gt b_1$$$。应用操作后,这些值将被交换。
在第三个测试用例中,应用操作后,$$$a = [1, 3]$$$ 和 $$$b = [2, 4]$$$。
在第四个测试用例中,应用操作后,$$$a = [1, 2]$$$ 和 $$$b = [3, 4]$$$。