1261 : Palm Island

Description

Toph is playing a card game. She has \(n\) cards and each card has a unique number of \(1,2\cdots n\). In this game, Toph can operate the deck of the cards. We may wish to assume that the cards from the top to the bottom of the deck are \(p_1,p_2,\cdots p_n\) (a permutation), then each operation must be one of the following two cases:

1. Place the top card at the bottom of the deck, that is, change the order of the deck into \(p_2,p_3\cdots p_n,p_1\).
2. Place the second card from the top at the bottom of the deck, that is, change the order of the deck into \(p_1,p_3\cdots p_n,p_2\)

Now, you know that the initial order(from top to bottom) of Toph’s deck is \(a_1,a_2,\cdots a_n\), and Toph wants to change the order of the deck into \(b_1,b_2,\cdots b_n\) after some operations. Please construct the operation sequence to help Toph implement the change.

Toph has no patience. So the number of operations should not exceed \(n^2\).

Input

The first line contains an integer \(T\) , indicating the number of test cases.

For each test case:

• The first line contains an integer, \(n(3\le n\le 1000)\), indicating the number of Toph’s cards.
• The second line contains \(n\) integers \(a_1,a_2,\cdots a_n\), a permutation indicating the order of the deck initially.
• The third line contains \(n\) integers \(b_1,b_2,\cdots b_n\), a permutation indicating the order of the deck want to make.

It is guaranteed that the sum of \(n\) in \(T\) test cases is not exceed \(1000\).

Output

For each test case:

• Output a line, which contains a string \(s_1s_2\dots s_k(s_i\in \{1,2\},\ 1\le i\le k)\) as your operation sequence. The length of the string should not exceed \(n^2\), or you will get “Wrong Answer”.
• If there are multiple solutions, output any of them.

Sample

2
3
1 2 3
2 3 1
4
1 2 3 4
2 1 3 4

1
112212

Hint

If \(a_1,a_2\cdots a_n\) and \(b_1,b_2\cdots b_n\) are the same in a test case, outputing an empty string is ok. But you should output an empty line in this situation.

DO NOT add extra space at the end of lines, or you will get “Wrong Answer” verdict.

Source

Author

FUDAN