Unstable String Sort

2000ms

262144K

Description:

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.

Input:

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$$$.

Output:

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.

Sample Input:

3 2
1 2 3
1 3 2

Sample Output:

YES
abb

Informação

Provedor Codeforces

Código CF1213F