Pawn Shop

문제

You run a tight ship at the pawn shop. You arrange certain items in the window to be displayed to the street. You sometimes display the same type of item multiple times. For simplicity, we think of the items on display as a sequence of values where the value represents the type of item being shown.

For example, your display could be this sequence: \[ 1~~2~~6~~2~~7~~9~~8~~5 \]

After coming back from your latest vacation, you find that your staff has completely rearranged the display by moving items around. Yikes! For example, the display above could be rearranged to: \[ 2~~6~~1~~2~~9~~7~~5~~8 \]

You fear this could be the cause of confusion and may scare off repeat customers. But you don't have time to move items back to their original positions.

As a compromise, you will put dividers up in the window to partition the displayed items into groups of consecutive items. Each group should be a rearrangement of the types of items that were in those positions in your preferred arrangement.

More precisely, let $a_1,\dots ,a_{N}a\_1,\; \backslash ldots,\; a\_N$ denote the first sequence and $b_1,\dots ,b_{N}b\_1,\; \backslash ldots,\; b\_N$ denote the second sequence. You may place dividers around $i,i+1,\dots ,ji,\; i+1,\; \backslash ldots,\; j$ if $b_i,b_{i+1},\dots ,b_{j}b\_i,\; b\_\{i+1\},\; \backslash ldots,\; b\_j$ is a rearrangement of $a_i,a_{i+1},\dots ,a_{j}a\_i,\; a\_\{i+1\},\; \backslash ldots,\; a\_j$. You do not need to put a divider at the beginning or end of the sequence. Note, if $a_i=b_{i}a\_i\; =\; b\_i$ then a group may be formed using just this single index $ii$.

With the sequences above, you could place dividers # at three positions as indicated here: \[ 2~~6~~1~~\texttt{#}~~2~~\texttt{#}~~7~~9~~\texttt{#}~~5~~8 \]

It is not possible to divide the sequence into more than four groups that have this property.

Given the two sequences, determine how to partition the new sequence into the maximum possible number of groups.

입력

The first line of input contains a single integer $NN$ ($1\le N\le 3000001\; \backslash leq\; N\; \backslash leq\; 300\backslash ,000$), which is the length of the two sequences.

The next line contains $NN$ integers $a_1,\dots ,a_{N}a\_1,\; \backslash ldots,\; a\_N$ ($1\le a_i\le {10}^{9}1\; \backslash leq\; a\_i\; \backslash leq\; 10^9$), which is the original sequence.

The next line contains $NN$ integers $b_1,\dots ,b_{N}b\_1,\; \backslash ldots,\; b\_N$ ($1\le b_i\le {10}^{9}1\; \backslash leq\; b\_i\; \backslash leq\; 10^9$), which is the rearranged sequence. The values $b_1,\dots ,b_{N}b\_1,\; \backslash ldots,\; b\_N$ are a rearrangement of the values $a_1,\dots ,a_{N}a\_1,\; \backslash ldots,\; a\_N$.

출력

Display the rearranged sequence with a valid and maximum placing of dividers (#).

If there are multiple possible solutions, display any of them.

8
1 2 6 2 7 9 8 5
2 6 1 2 9 7 5 8

2 6 1 # 2 # 9 7 # 5 8

4
1 1 2 1
2 1 1 1

2 1 1 # 1

3
1 2 5
2 5 1

2 5 1