Поликарп недавно создал новый веб сервис. Как в любом современном сервисе, в нем есть возможность авторизации. А это автоматически подразумевает угрозы безопасности.
Поликарп решил сохранять хеш пароля, полученный по следующему алгоритму:
- получить пароль \(p\), состоящий из строчных латинских букв, и перемешать буквы в нем, чтобы получить \(p'\) (\(p'\) может остаться равным \(p\));
- построить две случайные строки, состоящие из строчных латинских букв, \(s_1\) и \(s_2\) (любая из них может быть пустой);
- полученный хеш \(h = s_1 + p' + s_2\), где сложение — это склеивание строк.
Например, пусть пароль будет \(p =\) «abacaba». Тогда \(p'\) может быть равно «aabcaab». Случайные строки \(s1 =\) «zyx» и \(s2 =\) «kjh». Тогда \(h =\) «zyxaabcaabkjh».
Обратите внимание, что нельзя удалять или добавлять буквы в \(p\), чтобы получить \(p'\), можно только менять их порядок.
Теперь Поликарп просит вас помочь ему в реализации модуля проверки пароля. По данному паролю \(p\) и хешу \(h\), проверьте, что \(h\) может являться хешом пароля \(p\).
Вам нужно ответить на \(t\) наборов входных данных.
Выходные данные
На каждый набор входных данных выведите «YES», если данный хеш \(h\) может быть получен по данному паролю \(p\), и «NO» в противном случае.
Примечание
Первый набор входных данных объяснен в условии.
Во втором наборе входных данных и \(s_1\), и \(s_2\) пусты, а \(p'=\) «threetwoone» — это перемешанная \(p\).
В третьем наборе входных данных хеш нельзя получить из пароля.
В четвертом наборе входных данных \(s_1=\) «n», \(s_2\) пуста, а \(p'=\) «one» — это перемешанная \(p\) (даже несмотря на то, что они совпадают).
В пятом наборе входных данных хеш нельзя получить из пароля.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
abacaba
zyxaabcaabkjh
onetwothree
threetwoone
one
zzonneyy
one
none
twenty
ten
|
YES
YES
NO
YES
NO
|