У Васи есть три строки \(s\), \(a\) и \(b\), состоящие из первых \(k\) букв латинского алфавита.
Назовем паттерном строку длины \(k\), где каждая из первых \(k\) букв латинского алфавита встречается ровно один раз (таким образом, существует ровно \(k!\) различных паттернов). Применение паттерна \(p\) к строке \(s\) — это замена каждой буквы строки \(s\) на \(p_i\), где \(i\) – это порядковый номер этой буквы в латинском алфавите. Например, применив паттерн «bdca» к строке «aabccd» мы получим строку «bbdcca».
Васю интересует, существует ли такой паттерн, применив который к строке \(s\), он получит строку, лексикографически больше либо равную строки \(a\) и лексикографически меньше либо равную строки \(b\).
Если существует несколько подходящих паттернов, разрешается вывести любой.
Строка \(a\) лексикографически меньше строки \(b\), если существует такое \(i\) (\(1 \le i \le n\)), что \(a_i < b_i\), а для любого \(j\) (\(1 \le j < i\)) \(a_j = b_j\).
В этой задаче вам необходимо ответить на \(t\) независимых тестовых наборов.
Выходные данные
На каждый тестовый набор выведите ответ в следующем формате:
Если не существует подходящего паттерна, то в первой строке выведите «NO».
Иначе в первой строке выведите «YES», а во второй сам паттерн (\(k\) строчных букв, каждая из первых \(k\) букв латинского алфавита должна встретиться ровно один раз).
Если существует несколько подходящих паттернов — разрешается вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
bbcb
aada
aada
3
abc
bbb
bbb
|
YES
badc
NO
|