← 返回题目列表

Codeforces · 1085/E

E. Vasya 和模板

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

Vasya 拥有三个字符串 $$$s$$$ 、 $$$a$$$ 和 $$$b$$$ ,每个字符串仅由前 $$$k$$$ 拉丁字母组成。

令模板为长度为 $$$k$$$ 的字符串,使得前 $$$k$$$ 拉丁字母中的每一个都恰好在其中出现一次(因此存在 $$$k!$$$ 不同的模板)。将模板 $$$p$$$ 应用于字符串 $$$s$$$ 是将字符串 $$$s$$$ 中的每个字符替换为 $$$p_i$$$,$$$i$$$ 是该字母在字母表中的索引。例如,将模板“bdca”应用于字符串“aabccd”会生成字符串“bbdcca”。

Vasya 想知道是否存在这样一个模板,在将其应用于 $$$s$$$ 后,它会产生按字典顺序大于或等于字符串 $$$a$$$ 且按字典顺序小于或等于字符串 $$$b$$$ 的字符串。

如果存在多个合适的模板,则打印其中任何一个。

如果存在 $$$i$$$ ($$$1 \le i \le n$$$) 且 $$$a_i < b_i$$$ 并且对于任何 $$$j$$$ ($$$1 \le j < i$$$) $$$a_j = b_j$$$,则字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$。

您需要独立回答 $$$t$$$ 测试用例。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^6$$$) — 测试用例的数量。

在 hacks 中你只能使用 $$$t = 1$$$。

接下来的 $$$t$$$ 行包含以下形式的测试用例的描述:

测试用例的第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 26$$$) — 模板的长度。

测试用例的第二行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10^6$$$)。

测试用例的第三行包含字符串 $$$a$$$。

测试用例的第四行包含字符串 $$$b$$$。

字符串 $$$s$$$、$$$a$$$ 和 $$$b$$$ 具有相同的长度 ($$$|s| = |a| = |b|$$$),并且仅包含前 $$$k$$$ 拉丁字母,所有字母均为小写。

保证字符串 $$$a$$$ 按字典顺序小于或等于字符串 $$$b$$$。

还保证所有测试用例的字符串总长度不会超过 $$$3 \cdot 10^6$$$。

输出

按以下形式打印所有测试用例的答案:

如果不存在合适的模板,则在第一行打印“NO”。

否则在第一行打印“YES”,在第二行打印模板本身($$$k$$$小写字母,每个前$$$k$$$拉丁字母应该恰好出现一次)。

如果存在多个合适的模板,则打印其中任何一个。

示例

输入 #1

2
4
bbcb
aada
aada
3
abc
bbb
bbb

输出 #1

YES
badc
NO