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

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

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.

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.