32451번 - Cards 스페셜 저지다국어

문제

Diana is a student who likes to play various types of board games. Today, she receives a deck of cards from her teacher as her birthday gift!

The deck of cards is special: there are $n$ cards in the deck, and each card has a number on its front and another number on its back. Each number on the front or the back is an integer from 1ドル$ to $n$. Furthermore, all $n$ numbers on the front are unique, and so are the $n$ numbers on the back. In other words, numbers on the front and the back are two different permutations of numbers from 1ドル$ to $n$.

Apart from board games, Diana is also interested in mathematics and computer science. While she is playing with those cards, the concept of inversions in a permutation comes to her mind. An inversion is defined as a pair of indices $(i, j)$ such that $i<j$ and the element at position $i$ is greater than the element at position $j$. In other words, an inversion represents a situation where two elements are “out of order” relative to their positions. A permutation has inversion count $c$ if there are $c$ inversions can be found within it.

Diana wonders if she could rearrange the cards in some order so that the permutation on the front has the same inversion count as the permutation on the back (she cannot flip or throw away some cards). She cannot solve the problem in a while, so she wants to hear your solution.

In formal, you are given two permutations of integers from 1ドル$ to $n$: $a_1, a_2, \dots ,a_n$ and $b_1, b_2, \dots ,b_n$. You have to find another permutation of the first $n$ positive integers $p_1, p_2, \dots ,p_n,ドル such that $a' = [a_{p_1} , a_{p_2} ,\dots ,a_{p_n}]$ and $b' = [b_{p_1} , b_{p_2} ,\dots ,b_{p_n} ]$ have the same inversion count. Output the sequences $a'$ and $b'$.

입력

The first line of the input contains an integer $n,ドル denoting the number cards in the deck. The second line of the input contains $n$ integers $a_1, a_2,\dots ,a_n,ドル where $a_i$ is the number on the front of the $i$-th card. The third line of the input contains $n$ integers $b_1, b_2,\dots ,b_n,ドル where $b_i$ is the number on the back of the $i$-th card.

출력

If it is impossible to rearrange the cards so that the aforementioned condition is satisfied, print No. Otherwise, print Yes in the first line of the output. Then in the second line of the output, print $n$ integers $a'_1, a'_2, \dots ,a'_n,ドル denoting the numbers on the front of the cards after the rearrangement. In the third line of the output, print $n$ integers $b'_1, b'_2, \dots , b'_n,ドル denoting the numbers on the back of the cards after the rearrangement.

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

제한

• 1ドル ≤ n ≤ 5 \times 10^5$
• 1ドル ≤ a_i ≤ n$ for $i \in \{1, 2, \dots ,n\}$
• 1ドル ≤ b_i ≤ n$ for $i \in \{1, 2,\dots ,n\}$
• It is guaranteed that $a_1, a_2,\dots ,a_n$ and $b_1, b_2,\dots ,b_n$ are both permutations of integers 1,ドル 2, \dots ,n$.

힌트