26451번 - 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$ denotes the $i$-th element of $A,ドル and its value is an integer between 1ドル$ and $M,ドル and the same is true for $b_j,ドル which is the $j$-th element of the sequence $B$.

You can do a magic trick to the sequence $A$ only once: you can prepare a permutation $P = (p_1, \dots , p_M)$of integers from 1ドル$ through $M,ドル and can change the sequence $A$ to $A'$ by using $P$ as follows: $a'_i = p_{a_i}$ (1ドル \le i \le N$).

You want to make the distance between the sequence $A'$ and another sequence $B$ closer by changing $A$ to $A'$ through a magic trick. The "distance" between two sequences is defined as Hamming distance. The Hamming distance between two equal-length sequences is the number of positions at which the corresponding values are different.

Among all possible $A',ドル you have to find a sequence which satisfies all of the following conditions.

• No other possible sequences as $A'$ have a smaller distance to $B$ than the distance between this sequence and $B$.
• It is the lexicographically smallest sequence among possible sequences which has the same distance between $B$.

Here, a sequence $X = (x_1, x_2, \dots , x_N)$ is "lexicographically smaller" than another same length sequence $Y = (y_1, y_2, \dots , y_N)$ if and only if the following condition holds: there exists an index $i$ (1ドル \le i \le N$), such that $x_j = y_j$ for all indices $j$ (1ドル \le j < i$), and $x_i < y_i$.

입력

The input consists of a single test case of the following format.

$N$ $M$

$a_1$ $\dots$ $a_N$

$b_1$ $\dots$ $b_N$

The first line consists two integers $N$ (1ドル \le N \le 100,000円$) and $M$ (1ドル \le M \le 60$), which represent that the length of sequences are $N,ドル and each sequence has $N$ values between 1ドル$ and $M$.

The second line consists of $N$ integers. The $i$-th integer is denoted $a_i$ (1ドル \le a_i \le M$).

The third line consists of $N$ integers. The -th integer is denoted $b_i$ (1ドル \le b_i \le M$).

출력

Print $N$ integers, with spaces in between. The $i$-th integer should be the $i$-th element of a sequence which satisfies all conditions in the problem statement. Each element of a sequence should be printed as an integer.

제한

힌트