A12776 | Unstable String Sort

Authors have come up with the string $s$ consisting of $n$ lowercase Latin letters.

You are given two permutations of its indices (not necessary equal) $p$ and $q$ (both of length $n$ ). Recall that the permutation is the array of length $n$ which contains each integer from $1$ to $n$ exactly once.

For all $i$ from $1$ to $n-1$ the following properties hold: $s[p_i] \le s[p_{i + 1}]$ and $s[q_i] \le s[q_{i + 1}]$ . It means that if you will write down all characters of $s$ in order of permutation indices, the resulting string will be sorted in the non-decreasing order.

Your task is to restore any such string $s$ of length $n$ consisting of at least $k$ distinct lowercase Latin letters which suits the given permutations.

If there are multiple answers, you can print any of them.

The first line of the input contains two integers $n$ and $k$ ( $1 \le n \le 2 \cdot 10^5, 1 \le k \le 26$ ) — the length of the string and the number of distinct characters required.

The second line of the input contains $n$ integers $p_1, p_2, \dots, p_n$ ( $1 \le p_i \le n$ , all $p_i$ are distinct integers from $1$ to $n$ ) — the permutation $p$ .

The third line of the input contains $n$ integers $q_1, q_2, \dots, q_n$ ( $1 \le q_i \le n$ , all $q_i$ are distinct integers from $1$ to $n$ ) — the permutation $q$ .

If it is impossible to find the suitable string, print "NO" on the first line.

Otherwise print "YES" on the first line and string $s$ on the second line. It should consist of $n$ lowercase Latin letters, contain at least $k$ distinct characters and suit the given permutations.

If there are multiple answers, you can print any of them.