Unique Palindromes

Description:

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.

Sample 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

Sample 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.