← 返回题目列表

Codeforces · 1213/F

F. 不稳定的字符串排序

中文机器翻译题面 查看原题

作者提出了由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。

给出了其索引的两种排列(不一定相等)$$$p$$$ 和 $$$q$$$(长度均为 $$$n$$$)。回想一下,排列是长度为 $$$n$$$ 的数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好一次。

对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$,以下属性成立:$$$s[p_i] \le s[p_{i + 1}]$$$ 和 $$$s[q_i] \le s[q_{i + 1}]$$$。这意味着,如果您按照排列索引的顺序写下 $$$s$$$ 的所有字符,则生成的字符串将以非递减顺序排序。

你的任务是恢复任何长度为 $$$n$$$ 的此类字符串 $$$s$$$,其中至少包含 $$$k$$$ 不同的小写拉丁字母,且适合给定的排列。

如果有多个答案,您可以打印其中任何一个。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le k \le 26$$$) — 字符串的长度和所需的不同字符的数量。

输入的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, 所有 $$$p_i$$$ 都是从 $$$1$$$ 到 $$$n$$$ 的不同整数) — 排列 $$$p$$$。

输入的第三行包含 $$$n$$$ 整数 $$$q_1, q_2, \dots, q_n$$$ ($$$1 \le q_i \le n$$$, 所有 $$$q_i$$$ 都是从 $$$1$$$ 到 $$$n$$$ 的不同整数) — 排列 $$$q$$$。

输出

如果无法找到合适的字符串,请在第一行打印“NO”。

否则在第一行打印“YES”,在第二行打印字符串 $$$s$$$。它应由 $$$n$$$ 小写拉丁字母组成,至少包含 $$$k$$$ 不同字符并适合给定的排列。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3 2
1 2 3
1 3 2

输出 #1

YES
abb