给你两个排列$$$^{\text{*}}$$$ $$$a$$$ 和 $$$b$$$,长度均为$$$n$$$。
您可以对排列 $$$a$$$ 执行以下三步操作:
1. 选择索引 $$$i$$$ ($$$1 \le i \le n$$$)。
2. 将 $$$a_1, a_2, \ldots, a_{i-1}$$$ 向右循环移位 $$$1$$$。如果您选择 $$$i = 1$$$,则此范围不存在,并且您不会进行任何循环移位。
3. 将 $$$a_{i + 1}, a_{i + 2}, \ldots, a_n$$$ 向右循环移位 $$$1$$$。如果您选择 $$$i = n$$$,则此范围不存在,并且您不会进行任何循环移位。
运算后,$$$a_1,a_2,\ldots, a_{i-2},a_{i-1},a_i,a_{i + 1}, a_{i + 2},\ldots,a_{n-1}, a_n$$$ 转化为$$$a_{i-1},a_1,\ldots,a_{i-3},a_{i-2},a_i,a_n,a_{i + 1},\ldots,a_{n-2},a_{n-1}$$$。
以下是对长度为 $$$7$$$ 的恒等排列 $$$[1,2,3,4,5,6,7]$$$ 进行的操作的一些示例:
- 如果我们选择$$$i = 3$$$,它将变成$$$[2, 1, 3, 7, 4, 5, 6]$$$。
- 如果我们选择$$$i = 1$$$,它将变成$$$[1, 7, 2, 3, 4, 5, 6]$$$。
- 如果我们选择$$$i = 7$$$,它将变成$$$[6, 1, 2, 3, 4, 5, 7]$$$。
找到一个最多使用 $$$2n$$$ 运算的构造,使 $$$a$$$ 等于 $$$b$$$ 或打印 $$$-1$$$(如果不可能)。不需要最小化操作数量。可以证明,如果可以使 $$$a$$$ 等于 $$$b$$$,则可以在 $$$2n$$$ 操作内完成此操作。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) - 排列 $$$a$$$ 和 $$$b$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 排列 $$$a$$$ 的值。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — 排列 $$$b$$$ 的值。
保证所有测试用例的 $$$n$$$ 总和不会超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例:
如果存在将 $$$a$$$ 转换为 $$$b$$$ 的操作序列,则输出单个整数 $$$q$$$ ($$$0\le q\le 2n$$$) — 第一行中的操作数和 $$$q$$$ 整数,其中第 $$$i$$$ 个数字表示第二行中第 $$$i$$$ 个操作的索引。
如果没有操作顺序,则在唯一一行中输出$$$-1$$$。
示例
输入 #1
4 1 1 1 2 1 2 2 1 3 2 1 3 3 2 1 8 7 8 3 5 4 6 1 2 2 1 6 4 5 3 8 7
输出 #1
0 -1 2 1 3 7 3 4 5 1 2 1 1
注意
在第一种情况下,从$$$a=b$$$开始就不能进行任何操作。
第二种情况,可以证明$$$a$$$不能转化为$$$b$$$。
在第三种情况下,$$$a$$$ 在第一次操作后转换为 $$$[2,3,1]$$$,在第二次操作后转换为 $$$b$$$。