D. Уникальные палиндромы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Палиндром — это строка, которая читается одинаково с обеих сторон. Например, строка abcba — палиндром, а строка abca — нет.

Пусть $$$p(t)$$$ — это количество уникальных палиндромных подстрок строки $$$t$$$, т.е. количество подстрок $$$t[l \dots r]$$$, которые сами являются палиндромами. Даже если некоторые подстроки присутствуют в $$$t$$$ несколько раз, они учитываются ровно один раз. (Вся строка $$$t$$$ также является подстрокой $$$t$$$).

Например, строка $$$t$$$ $$$=$$$ 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($$$abcbbcabcb$$$, 5)$$$ $$$=$$$ $$$p($$$abcbb$$$) = 5$$$.

Вам даны целое число $$$n$$$ и $$$k$$$ «условий» ($$$k \le 20$$$). Назовем строку $$$s$$$, состоящую из $$$n$$$ строчных латинских букв, хорошей если все $$$k$$$ условий удовлетворены одновременно. Условие — это пара $$$(x_i, c_i)$$$, обозначающая что:

  • $$$p(s, x_i) = c_i$$$, то есть префикс строки $$$s$$$ длины $$$x_i$$$ содержит ровно $$$c_i$$$ уникальных палидромных подстрок.
Найдите хорошую строку $$$s$$$ или сообщите, что такой $$$s$$$ нет.

Изучите примечание, если вам нужны дополнительные пояснения.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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 < x_2 < \dots < 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$$$.

Выходные данные

Для каждого набора входных данных если нет хорошей строки $$$s$$$ длины $$$n$$$, которая удовлетворяет всем запросам, выведите NO.

Иначе, выведите YES и строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв, которая удовлетворяет всем запросам. Если есть несколько ответов, выведите любой из них.

Пример
Входные данные
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
Выходные данные
YES
abcbbcabcb
YES
foo
YES
ayda
YES
wada
NO
YES
abcbcacbab
NO
Примечание

В первом наборе строка $$$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.