D. Unique Palindromes

A palindrome is a string that reads the same backwards as forwards. For example, the string abcba is palindrome, while the string abca is not.

Let $p(t)$ be the number of unique palindromic substrings of string $t$, i. e. the number of substrings $t[l \dots r]$ that are palindromes themselves. Even if some substring occurs in $t$ several times, it's counted exactly once. (The whole string $t$ is also counted as a substring of $t$).

For example, string $t$ $=$ abcbbcabcb has $p(t) = 6$ unique palindromic substrings: a, b, c, bb, bcb and cbbc.

Now, let's define $p(s, m) = p(t)$ where $t = s[1 \dots m]$. In other words, $p(s, m)$ is the number of palindromic substrings in the prefix of $s$ of length $m$. For example, $p($abcbbcabcb$, 5)$ $=$ $p($abcbb$) = 5$.

You are given an integer $n$ and $k$ "conditions" ($k \le 20$). Let's say that string $s$, consisting of $n$ lowercase Latin letters, is good if all $k$ conditions are satisfied at the same time. A condition is a pair $(x_i, c_i)$ and have the following meaning:

• $p(s, x_i) = c_i$, i. e. a prefix of $s$ of length $x_i$ contains exactly $c_i$ unique palindromic substrings.

Find a good string $s$ or report that such $s$ doesn't exist.
Look in Notes if you need further clarifications.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($3 \le n \le 2 \cdot 10^5$; $1 \le k \le 20$) — length of good string $s$ and number of conditions.

The second line of each test case contains $k$ integers $x_1, x_2, \dots, x_k$ ($3 \le x_1 < x_2 < \dots < x_k = n$) where $x_i$ is the length of the prefix in the $i$-th condition.

The third line of each test case contains $k$ integers $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)}$) where $c_i$ is the number of palindromic substrings in the $i$-th condition.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$.

Output

For each test case, if there is no good string $s$ of length $n$ that satisfies all conditions, print NO.

Otherwise, print YES and a string $s$ of length $n$, consisting of lowercase Latin letters, that satisfies all conditions. If there are multiple answers, print any of them.

Example

input

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

output

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

Note

In the first test case, string $s$ $=$ abcbbcabcb satisfies $k = 2$ conditions:

• $p(s, x_1) = p(s, 5) =$ $p($abcbb$) = 5 = s_1$. Palindromic substrings are a, b, c, bb and bcb.
• $p(s, x_2) = p(s, 10) =$ $p($abcbbcabcb$) = 6 = s_2$. Palindromic substrings are the same as above, and one extra substring cbbc.

In the second test case, string foo satisfies $k = 1$ condition:

• $p($foo$) = 3$. Palindromic substrings are f, o and oo.

There are other possible answers.
In the third test case, string ayda satisfies $k = 2$ conditions:

• $p($ayd$) = 3$. Palindromic substrings are a, y and d.
• $p($ayda$) = 3$. Palindromic substrings are the same.

In the fourth test case, string wada satisfies $k = 2$ conditions:

• $p($wad$) = 3$. Palindromic substrings are w, a and d.
• $p($wada$) = 4$. Palindromic substrings are the same, and one extra substring ada.

In the fifth test case, it can be proven that there is no string of length $4$ which has $5$ palindromic substrings.

In the sixth test case, string abcbcacbab satisfies $k = 3$ conditions:

• $p($abcb$) = 4$. Palindromic substrings are a, b, c and bcb.
• $p($abcbca$) = 5$. Palindromic substrings are the same, and one extra substring cbc.
• $p($abcbcacbab$) = 8$. Palindromic substrings are the same, and three extra substrings cac, bab and bcacb.

解题思路

　　先手动模拟$n$较小的情况，看看唯一回文子串个数$P$是多少。

　　如果$n=1$，那么$P=1$。

　　如果$n=2$，只有两种情况 aa 和 ab ，都有$P=2$。

　　如果$n=3$，有$4$种情况，即分别考虑第$2$个与第$3$个字符是否与前一个相同，那么就有$2^2$种。即 aaa，aab，aba，abc，都有$P=3$。这也是为什么数据中的$x$和$c$都至少为$3$。

　　如果$n > 3$，那么前$3$个字符对$P$已经有$3$个贡献，如果往字符串最后添加一个字符$c$，那么新的字符串的$P_{new}$只能比之前的$P_{old}$增加$0$或$1$。反证法，假设$P_{new} - P_{old} \ge 2$，那么选择出两个新的回文子串，这两个新的回文子串的结尾字符必然是$c$，并且这两个回文子串的长度必然不一样。不妨设长度大的子串$s_1$的左端点为$i$，长度小的子串$s_2$的左端点为$j$，那么有$i < j$，两个回文子串的右端点均为$k$（即字符$c$的位置）。根据回文的定义，$s_2$必然是$s_1$的前缀与后缀，可以参考下图：

　　回文子串$[j, \ k]$与$[i, \ i+k-j]$是同一个，而我们已经把前面的$[i,i+k-j]$统计到$P_{old}$了。所以如果存在以$c$结尾的回文子串那么应该只统计长度最长的那一个，因为任何短的回文子串在之前已经统计过了。故多加一个字符最多会使得$P$增加$1$。

　　我们先构造出一些特别的子串，$P=n$时有 aaaaaa... ；$P=3$时有 abcabc... 。

　　然后我们先考虑$k=1$的情况，即只有一个约束条件。首先根据上面的结论知道如果$c_1 > x_1$，那么无解。否则先构造出$c_1 - 3$个 a（注意$c_i \geq 3$），然后用 abc 填补直到字符串的长度为$n$。那么就会得到这种形式：aaa...aaabcabc... 。

　　考虑$k>1$。首先如果$c_{i} - c_{i-1} > x_{i} - x_{i-1}$，那么无解，因为添加$x_i - x_{i-1}$个字符最多使得$P$增加$x_i - x_{i-1}$。否则我们任取一个之前没用过的字符$d$（由于最多只有$20$个约束，因此$26$个小写字母足够用），然后往答案后面添加$c_{i} - c_{i-1}$个$d$，然后再用 abc 去填充直到字符的长度变成$x_i$。那么得到的字符串就会是这种形式，其中表示 | 各个约束的边界： aaaaaaaaabcabcab|dddddcabcabca|eeebcab 。

　　注意到每次填充 abc 都是从上一次结束字符的下一个开始，比如上一次约束最后填充到 a ，那么下一次应该从 b 开始继续填充，这样做可以避免产生不必要的回文。否则比如 ...ddabca|eabc... ，那么就会形成回文 aea 。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 2e5 + 10;
 5 
 6 int x[N], c[N];
 7 
 8 void solve() {
 9     int n, m;
10     scanf("%d %d", &n, &m);
11     for (int i = 0; i < m; i++) {
12         scanf("%d", x + i);
13     }
14     for (int i = 0; i < m; i++) {
15         scanf("%d", c + i);
16     }
17     if (c[0] > x[0]) {    // P<=n 
18         printf("NO\n");
19         return;
20     }
21     string ans;
22     int t = 0;
23     // 处理第一个约束 
24     for (int i = 0; i < c[0] - 3; i++) {
25         ans += 'a';
26     }
27     for (int i = c[0] - 3; i < x[0]; i++) {
28         ans += 'a' + t;
29         t = (t + 1) % 3;
30     }
31     //处理剩下的约束 
32     for (int i = 1; i < m; i++) {
33         if (c[i] - c[i - 1] > x[i] - x[i - 1]) {
34             printf("NO\n");
35             return;
36         }
37         for (int j = c[i - 1]; j < c[i]; j++) {    // 添加c[i]-c[i-1]个之前没出现过的字符 
38             ans += 'c' + i;
39         }
40         while (ans.size() < x[i]) {    // 用abc填补到长度x[i] 
41             ans += 'a' + t;
42             t = (t + 1) % 3;
43         }
44     }
45     while (ans.size() < n) {    // 记得最后把字符串填补到长度n 
46         ans += 'a' + t;
47         t = (t + 1) % 3;
48     }
49     printf("YES\n%s\n", ans.c_str());
50 }
51 
52 int main() {
53     int t;
54     scanf("%d", &t);
55     while (t--) {
56         solve();
57     }
58     
59     return 0;
60 }

参考资料

　　Codeforces Round #868 (Div.2) Editorial：https://codeforces.com/blog/entry/115465