H. Peak Productivity Forces
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
I'm peakly productive and this is deep.

You are given two permutations$$$^{\text{∗}}$$$ $$$a$$$ and $$$b$$$, both of length $$$n$$$.

You can perform the following three-step operation on permutation $$$a$$$:

  1. Choose an index $$$i$$$ ($$$1 \le i \le n$$$).
  2. Cyclic shift $$$a_1, a_2, \ldots, a_{i-1}$$$ by $$$1$$$ to the right. If you had chosen $$$i = 1$$$, then this range doesn't exist, and you cyclic shift nothing.
  3. Cyclic shift $$$a_{i + 1}, a_{i + 2}, \ldots, a_n$$$ by $$$1$$$ to the right. If you had chosen $$$i = n$$$, then this range doesn't exist, and you cyclic shift nothing.

After the operation, $$$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$$$ is transformed into $$$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}$$$.

Here are some examples of operations done on the identity permutation $$$[1,2,3,4,5,6,7]$$$ of length $$$7$$$:

  • If we choose $$$i = 3$$$, it will become $$$[2, 1, 3, 7, 4, 5, 6]$$$.
  • If we choose $$$i = 1$$$, it will become $$$[1, 7, 2, 3, 4, 5, 6]$$$.
  • If we choose $$$i = 7$$$, it will become $$$[6, 1, 2, 3, 4, 5, 7]$$$.
Notably, position $$$i$$$ is not shifted.

Find a construction using at most $$$2n$$$ operations to make $$$a$$$ equal to $$$b$$$ or print $$$-1$$$ if it is impossible. The number of operations does not need to be minimized. It can be shown that if it is possible to make $$$a$$$ equal to $$$b$$$, it is possible to do this within $$$2n$$$ operations.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the lengths of permutations $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the values of permutation $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — the values of permutation $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$5 \cdot 10^5$$$.

Output

For each test case:

If there is a sequence of operations to transform $$$a$$$ into $$$b$$$, output a single integer $$$q$$$ ($$$0\le q\le 2n$$$) — the number of operations in the first line and $$$q$$$ integers with the $$$i$$$-th number representing the index of the $$$i$$$-th operation in the second line.

If there is no sequence of operations, output $$$-1$$$ in the only line.

Example
Input
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
Output
0

-1
2
1 3
7
3 4 5 1 2 1 1
Note

In the first case, you can do no operation since $$$a=b$$$.

In the second case, it can be proved $$$a$$$ can not be transformed into $$$b$$$.

In the third case, $$$a$$$ is transformed into $$$[2,3,1]$$$ after the first operation and into $$$b$$$ after the second operation.