Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Unstable String Sort

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAuthors 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.

Example

Input

3 2 1 2 3 1 3 2

Output

YES abb

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/17/2020 02:22:19 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|