回文是向后读与向前读相同的字符串。例如,字符串 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。