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.

回文串是指正读和反读都相同的字符串。例如，字符串 abcba 是回文串，而字符串 abca 则不是。

令 $p(t)$ 表示字符串 $t$ 中不同回文子串的个数，即满足 $t[l \dots r]$ 本身为回文串的子串个数。即使某个子串在 $t$ 中多次出现，也仅计一次。（整个字符串 $t$ 本身也被视为它的一个子串。）

例如，字符串 $t = \text{abcbbcabcb}$ 有 $p(t) = 6$ 个不同的回文子串：a、b、c、bb、bcb 和 cbbc。

现在，定义 $p(s, m) = p(t)$，其中 $t = s[1 \dots m]$。换言之，$p(s, m)$ 表示字符串 $s$ 的长度为 $m$ 的前缀中所含回文子串的个数。例如，$p(\text{abcbbcabcb}, 5) = p(\text{abcbb}) = 5$。

给定一个整数 $n$ 和 $k$ 个“条件”（$k \le 20$）。称一个由 $n$ 个小写拉丁字母组成的字符串 $s$ 是好的，当且仅当它同时满足全部 $k$ 个条件。每个条件是一个二元组 $(x_i, c_i)$，其含义如下：

• $p(s, x_i) = c_i$，即 $s$ 的长度为 $x_i$ 的前缀中恰好包含 $c_i$ 个不同的回文子串。

请找出一个“好的”字符串 $s$；若不存在这样的字符串，则报告无解。

如需进一步澄清，请参阅“说明”部分。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $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 \lt x_2 \lt \dots \lt 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$。

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.

对于每个测试用例，若不存在满足所有条件的长度为 $n$ 的好字符串 $s$，则输出 NO。

否则，输出 YES 以及一个长度为 $n$、由小写拉丁字母组成的字符串 $s$，该字符串需满足所有条件。若存在多个答案，输出任意一个即可。

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.

在第一个测试用例中，字符串 $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。