Авторы загадали строку \(s\), состоящую из \(n\) строчных букв латинского алфавита.
Вам задано две перестановки ее индексов (не обязательно одинаковых) \(p\) и \(q\) (обе длины \(n\)). Напомним, что перестановкой называется массив длины \(n\), содержащий каждое целое число от \(1\) до \(n\) ровно один раз.
Для всех \(i\) от \(1\) до \(n-1\) выполняются следующие свойства: \(s[p_i] \le s[p_{i + 1}]\) и \(s[q_i] \le s[q_{i + 1}]\). Это значит, что если вы выпишете все символы \(s\) в порядке индексов в перестановке, результирующая строка получится отсортированной в неубывающем порядке.
Ваша задача — восстановить любую строку \(s\) длины \(n\), состоящую хотя бы из \(k\) различных строчных букв латинского алфавита, которая подходит к заданным перестановкам.
Если существует несколько возможных ответов, вы можете вывести любой.
Выходные данные
Если невозможно найти подходящую строку, выведите «NO» в первой строке.
Иначе выведите «YES» в первой строке и строку \(s\) во второй строке. Она должна состоять ровно из \(n\) строчных букв латинского алфавита, содержать хотя бы \(k\) различных символов и подходить заданным перестановкам.
Если существует несколько возможных ответов, вы можете вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2 3
1 3 2
|
YES
abb
|