← 返回题目列表

Codeforces · 1823/D

D. 独特的回文

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

回文是向后读与向前读相同的字符串。例如,字符串 abcba 是回文,而字符串 abca 则不是。

令 $$$p(t)$$$ 为字符串 $$$t$$$ 的唯一回文子串的数量,i。 e.本身是回文的子串 $$$t[l \dots r]$$$ 的数量。即使某些子字符串在 $$$t$$$ 中出现多次,它也只计算一次。 (整个字符串 $$$t$$$ 也算作 $$$t$$$ 的子字符串)。

例如,字符串 $$$t$$$ $$$=$$$ abcbbcabcb 具有 $$$p(t) = 6$$$ 唯一回文子串:a、b、c、bb、bcb 和 cbbc。

现在,让我们定义 $$$p(s, m) = p(t)$$$,其中 $$$t = s[1 \dots m]$$$。换句话说,$$$p(s, m)$$$ 是长度为$$$m$$$ 的$$$s$$$ 前缀中回文子串的数量。例如,$$$p($$$abcbbcabcb$$$, 5)$$$ $$$=$$$ $$$p($$$abcbb$$$) = 5$$$。

给你一个整数 $$$n$$$ 和 $$$k$$$ “条件” ($$$k \le 20$$$)。假设字符串 $$$s$$$ 由 $$$n$$$ 小写拉丁字母组成,如果同时满足所有 $$$k$$$ 条件,则该字符串很好。条件是一对 $$$(x_i, c_i)$$$ 并具有以下含义:

- $$$p(s, x_i) = c_i$$$, i。 e.长度为 $$$x_i$$$ 的前缀 $$$s$$$ 恰好包含 $$$c_i$$$ 唯一的回文子串。

如果您需要进一步说明,请查看注释。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 20$$$) - 良好字符串 $$$s$$$ 的长度和条件数量。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$x_1, x_2, \dots, x_k$$$ ($$$3 \le x_1 < x_2 < \dots < x_k = n$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 条件中前缀的长度。

每个测试用例的第三行包含 $$$k$$$ 整数 $$$c_1, c_2, \dots, c_k$$$ ($$$3 \le c_1 \le c_2 \le \dots \le c_k \le \min{\left(10^9, \frac{(n + 1) n}{2} \right)}$$$) 其中$$$c_i$$$ 是第 $$$i$$$ 条件中的回文子串的数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$。

输出

对于每个测试用例,如果没有满足所有条件、长度为$$$n$$$的好字符串$$$s$$$,则打印NO。

否则,打印 YES 和长度为 $$$n$$$ 的字符串 $$$s$$$,由小写拉丁字母组成,满足所有条件。如果有多个答案,请打印其中任何一个。

示例

输入 #1

7
10 2
5 10
5 6
3 1
3
3
4 2
3 4
3 3
4 2
3 4
3 4
4 1
4
5
10 3
4 6 10
4 5 8
10 4
4 6 7 10
4 5 7 8

输出 #1

YES
abcbbcabcb
YES
foo
YES
ayda
YES
wada
NO
YES
abcbcacbab
NO

注意

在第一个测试用例中,字符串 $$$s$$$ $$$=$$$ abcbbcabcb 满足 $$$k = 2$$$ 条件:

- $$$p(s, x_1) = p(s, 5) =$$$ $$$p($$$abcbb$$$) = 5 = s_1$$$。回文子串是 a、b、c、bb 和 bcb。
- $$$p(s, x_2) = p(s, 10) =$$$ $$$p($$$abcbbcabcb$$$) = 6 = s_2$$$。回文子串同上,多了一个子串cbbc。

在第二个测试用例中,字符串 foo 满足 $$$k = 1$$$ 条件:

- $$$p($$$foo$$$) = 3$$$。回文子串是 f、o 和 oo。

在第三个测试用例中,字符串 ayda 满足 $$$k = 2$$$ 条件:

- $$$p($$$ayd$$$) = 3$$$。回文子串是 a、y 和 d。
- $$$p($$$ayda$$$) = 3$$$。回文子串是相同的。

在第四个测试用例中,字符串 wada 满足 $$$k = 2$$$ 条件:

- $$$p($$$wad$$$) = 3$$$。回文子串是 w、a 和 d。
- $$$p($$$wada$$$) = 4$$$。回文子串是相同的,多了一个子串ada。

在第五个测试用例中,可以证明不存在长度为$$$4$$$的字符串包含$$$5$$$回文子串。

在第六个测试用例中,字符串 abcbcacbab 满足 $$$k = 3$$$ 条件:

- $$$p($$$abcb$$$) = 4$$$。回文子串是 a、b、c 和 bcb。
- $$$p($$$abcbca$$$) = 5$$$。回文子串相同,多一个子串cbc。
- $$$p($$$abcbcacbab$$$) = 8$$$。回文子串相同,多了三个子串 cac、bab 和 bcacb。