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