D. PLUSworld
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer John is building PLUSworld, a giant barn complex with $$$n$$$ barns numbered from $$$1$$$ to $$$n$$$. For each $$$1 \le i \le n$$$, there is currently a one-way walkway from barn $$$i$$$ to barn $$$a_i$$$.

Before opening PLUSworld, Farmer John wants to reconfigure the roads so that, for every $$$1 \le i \le n$$$, the road from barn $$$i$$$ points to barn $$$b_i$$$. The target roads have the special property that each road points to its own barn or to a higher-numbered barn $$$(i \le b_i)$$$.

To do this, he sends Bessie to one barn of his choice. Let $$$p$$$ be the barn where Bessie is currently located. Bessie may perform the following operations any number of times:

  • Operation $$$1$$$: Increase the destination of the road from the current barn by $$$1$$$. More formally, set $$$a_p := a_p + 1$$$. This operation may only be performed if $$$a_p \lt n$$$.
  • Operation $$$2$$$: Follow the road from the current barn. More formally, set $$$p := a_p$$$.

Operation $$$1$$$ changes the array $$$a$$$, but Bessie stays at the same barn. Operation $$$2$$$ changes Bessie's current barn, but does not change the array.

Your goal is to make the array $$$a$$$ equal to the array $$$b$$$.

Determine whether this is possible. If it is possible, output any valid starting barn and any sequence of operations that makes $$$a=b$$$.

It can be shown that if a solution exists, then there exists one using at most $$$2n^2$$$ operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$\color{red}{i\le b_i}\le n$$$).

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$1000^2$$$.

Output

For each test case, if it is impossible to make $$$a$$$ equal to $$$b$$$, output a single integer $$$-1$$$.

Otherwise, output two lines.

On the first line, output two integers $$$o$$$ and $$$p$$$ — the number of operations you will perform and the initial index you choose ($$$0 \leq o \leq 2n^2$$$, $$$1 \leq p \leq n$$$).

On the second line, output $$$o$$$ integers $$$c_1,c_2,\ldots,c_o$$$ ($$$1\le c_i\le 2$$$), where $$$c_i$$$ is the type of the $$$i$$$-th operation.

If $$$c_i=1$$$, you perform operation $$$1$$$ and set $$$a_p:=a_p+1$$$. This operation may only be used if $$$a_p \lt n$$$ at that moment.

If $$$c_i=2$$$, you perform operation $$$2$$$ and set $$$p:=a_p$$$.

After performing all $$$o$$$ operations, the array $$$a$$$ must be equal to $$$b$$$.

If there are multiple valid answers, you may output any of them.

Example
Input
9
3
1 2 3
2 3 3
2
2 2
1 2
5
1 1 1 4 5
2 3 4 5 5
3
1 1 1
1 2 3
3
1 1 1
3 2 3
3
1 1 3
1 2 3
4
1 1 1 4
3 3 4 4
4
1 4 3 4
1 4 3 4
5
1 3 4 5 4
2 3 4 5 5
Output
5 1
1 2 1 2 2 
-1
12 1
1 2 1 1 2 1 1 1 2 1 2 2 
-1
-1
2 2
1 2 
12 1
1 1 2 1 2 1 1 2 1 1 2 2 
0 1
7 1
1 2 2 2 2 1 2
Note

For the first test case, Bessie starts at barn $$$1$$$. She increases $$$a_1$$$ from $$$1$$$ to $$$2$$$, follows the road to barn $$$2$$$, and increases $$$a_2$$$ from $$$2$$$ to $$$3$$$. The resulting array is $$$[2,3,3]$$$, which is equal to $$$b$$$.

For the second test case, $$$a_1=2 \gt b_1=1$$$. Since road destinations can only be increased, it is impossible to make $$$a_1$$$ equal to $$$b_1$$$, so the answer is $$$-1$$$.

For the third test case, Bessie starts at barn $$$1$$$. She changes $$$a_1$$$ from $$$1$$$ to $$$2$$$ and follows the road to barn $$$2$$$. She then changes $$$a_2$$$ from $$$1$$$ to $$$3$$$ and moves to barn $$$3$$$, changes $$$a_3$$$ from $$$1$$$ to $$$4$$$ and moves to barn $$$4$$$, and finally changes $$$a_4$$$ from $$$4$$$ to $$$5$$$. The resulting array is $$$[2,3,4,5,5]$$$, which is equal to $$$b$$$.