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 \lt x_2 \lt \dots \lt 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.

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.

Idx	Name	Rating
A	A-characteristic	800
B	Sort with Step	900
C	Strongly Composite	1300
D	Unique Palindromes	1900
E	Removing Graph	2500
F	Random Walk	2600

Codeforces Round 868 (Div. 2)