Troy is fleshing out the details of his latest initiative, HackCCO! Everyone knows that the biggest appeal of any hackathon is the free food. As such, to ensure the unparalleled success of HackCCO, Troy ordered a comically large cart stacked with $N$ pizzas where the $i$-th pizza from the top of the cart has flavour $a_i$.

After the pizza cart arrives, Troy needs to arrange them into some number of stacks on a long table. To do this, he takes the pizzas one-by-one from the top of the cart and moves them onto the table, each time either placing the pizza on top of another stack of pizzas or forming a new stack on the table.

The $N$ hungry HackCCO participants are lined up to get pizza from the table, one-by-one. Troy knows that the $i$-th person in line has a favourite pizza flavour of $b_i$. When the $i$-th person walks up to the table, if they see any pizzas of their favourite flavour at the top of any stack they will take any one of them at random. Otherwise, they won't take anything and will leave the table hungry.

Of course, hungry coders are not happy coders, so Troy doesn't want anyone to leave the table hungry. Thus, he asks you to help him find an arrangement of pizzas on the table such that it is possible for nobody to leave hungry. Furthermore, out of all such arrangements, Troy wants you to find one that creates the smallest number of stacks on the table (after all, tables can only get so long). Help him find such an arrangement or determine that it's impossible!

Input Specification

The first line of input contains a single integer $N$.

The second line of input contains $N$ space-separated integers $a_1,\dots ,a_N$ $(1\le a_i\le N)$.

The third line of input contains $N$ space-separated integers $b_1,\dots ,b_N$ $(1\le b_i\le N)$.

Marks Awarded	Bounds on $N$	Additional constraints
3 marks	$1\le N\le {10}^6$	$1\le a_i,b_i\le 2$
4 marks	$1\le N\le 5000$	All $a_i$ are distinct
5 marks	$1\le N\le {10}^6$	All $a_i$ are distinct
6 marks	$1\le N\le 5000$	None
7 marks	$1\le N\le {10}^6$	None

[Post-CCO edit: Subtasks 4 and 5 may not be solvable efficiently. CCO competitors were judged only on subtasks 1-3.]

Output Specification

If it is impossible to arrange the pizzas as desired, output -1.

Otherwise, your output should consist of three lines.

On the first line, output $K$, the minimum number of stacks required.

On the second line, output $N$ space-separated integers $c_1,\dots ,c_N$ $(1\le c_i\le K)$, indicating that the $i$-th pizza should be placed on stack $c_i$.

On the third line, output $N$ space-separated integers $d_1,\dots ,d_N$ $(1\le d_i\le K)$, indicating that the $i$-th person in line takes their pizza from the $d_i$-th stack.

This stack must have a pizza of flavour $b_i$ at the top when the $i$-th participant walks up to get their pizza.

Sample Input 1

7
1 2 3 2 2 1 3
2 3 1 2 3 2 1

Sample Output 1

2
1 2 1 2 1 2 2
1 2 2 2 1 2 1

Explanation for Sample 1

An illustration of the arrangement of pizzas on the table is shown above where red, yellow, and blue boxes represent pizzas of flavours $1$, $2$, and $3$ respectively.

Sample Input 2

2
1 2
1 1

Sample Output 2

-1