Permutation Magic

There are sequences $A = (a_1, \dots, a_N)$ and $B = (b_1, \dots, b_N)$ with the same length $N$. $a_i$ is the $i$-th element of $A$, and its value is an integer between $1$ and $M$. The same holds for $b_j$, the $j$-th element of $B$.

You can apply a magic trick to $A$ exactly once. Prepare a permutation $P = (p_1, \dots, p_M)$ of the integers from $1$ through $M$, and change $A$ into $A'$ by setting $a'_i = p_{a_i}$ ($1 \le i \le N$).

You want $A'$ to be closer to $B$ after the trick. The distance between two sequences is the Hamming distance, which is the number of positions where the corresponding values differ.

Among all possible $A'$, find a sequence that satisfies both of the following conditions.

• No other possible $A'$ has a smaller distance to $B$ than this sequence.
• Among the possible sequences with that same distance to $B$, it is the lexicographically smallest.

A sequence $X = (x_1, \dots, x_N)$ is lexicographically smaller than $Y = (y_1, \dots, y_N)$ if there is an index $i$ such that $x_j = y_j$ for all $j < i$ and $x_i < y_i$.

The input is given in the following format.

$N$ $M$

$a_1$ $\dots$ $a_N$

$b_1$ $\dots$ $b_N$

The first line contains two integers $N$ ($1 \le N \le 100{,}000$) and $M$ ($1 \le M \le 60$). Each sequence has $N$ values between $1$ and $M$.

The second line contains $N$ integers, where the $i$-th integer is $a_i$ ($1 \le a_i \le M$).

The third line contains $N$ integers, where the $i$-th integer is $b_i$ ($1 \le b_i \le M$).

Print $N$ integers separated by spaces. The $i$-th integer is the $i$-th element of a sequence that satisfies all the conditions above. Print each element as an integer.