Peak Productivity Forces
Contest: Codeforces Global Round 27
Difficulty rating: 3500
Tags: constructive algorithms

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]$$$.

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.

Input format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

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

Example output:
0

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

Editorial:
We can rephrase the problem as sorting $$$b^{-1}(a)$$$.
First, it is impossible to sort the permutation $$$[2, 1]$$$ because no operations you make affect the permutation.
Instead of completely sorting it we can get it to a semi sorted state in $$$n + 1$$$ moves. This semi sorted state will be: some pairs of non-intersecting adjacent elements will be swapped and $$$n$$$ will always be in its position at the very end.
ex: $$$[2, 1, 3, 5, 4, 6]$$$ where $$$1, 2$$$ are swapped and $$$4, 5$$$ are swapped
How we can reach the semi sorted state?
We will try to build this up in the prefix from largest element to smallest element. To move $$$x$$$ at index $$$i$$$ to the front we can do an operation on $$$i + 1$$$ if $$$i < n$$$.
Because our sorted state condition requires $$$n$$$ to be at the front, if $$$i = n$$$ and $$$x = n$$$ we can make a query on position $$$1$$$ and then position $$$3$$$ to insert it into the front.
If $$$i = n$$$ we can move $$$x - 1$$$ to the front and then $$$x$$$. Let $$$i'$$$ be the new position of $$$x$$$ after moving $$$x - 1$$$ to the front. If $$$i' = n$$$, we can move $$$x$$$ to it's correct position by doing the operation on position $$$1$$$. Otherwise, we can do the operation on position $$$i' + 1$$$ and insert it into the front.
From here we can make $$$n - 1$$$ more operations on either position $$$n$$$ or $$$n - 1$$$ depending on which one we need to send to the front to sort it properly.
We now need to be able to simulate the following operations efficiently.
1. Do the operation on index $$$i$$$.
2. Find the index of element $$$v$$$.
3. Find the element at index $$$i$$$.
This can be done in $$$O(\log n)$$$ amortized per operation using an implicit BBST using a treap or splay. Alternatively, we can index each value by $$$\text{current time} - \text{position}$$$. The general rotation to the right does not affect this index, but the positions that do not just shift to the right by $$$1$$$ must be manually updated. This takes $$$O(1)$$$ per update and $$$O(1)$$$ per query (for more information, read the code). Depending on the data structure used, the final complexity is either $$$O(n)$$$ or $$$O(n \log n)$$$.