Палиндром — это строка, которая читается одинаково с обеих сторон. Например, строка 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\) нет.
Изучите примечание, если вам нужны дополнительные пояснения.
Выходные данные
Для каждого набора входных данных если нет хорошей строки \(s\) длины \(n\), которая удовлетворяет всем запросам, выведите NO.
Иначе, выведите YES и строку \(s\) длины \(n\), состоящую из строчных латинских букв, которая удовлетворяет всем запросам. Если есть несколько ответов, выведите любой из них.
Примечание
В первом наборе строка \(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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|