Настали тяжелые времена. Сегодня Пете нужно набрать на экзамене по информатике 100 баллов. Все задачи на экзамене Пете кажутся простыми, но он боится, что не успеет сделать одну из них за такой маленький промежуток времени, поэтому он обратился к вам за помощью.
В условии даётся шаблон (строка, состоящая из строчных латинских букв, символов «?» и «*»). Известно, что символ «*» встречается в шаблоне не более одного раза.
Также в условии даны n строк-запросов, и для каждой необходимо определить, подходит ли она под данный шаблон, или нет.
Все было бы хорошо, но специальные символы в шаблоне в этой задаче действуют не так, как обычно!
Строка подходит под шаблон, если можно в шаблоне заменить каждый из символов «?» на одну хорошую строчную латинскую букву, а символ «*» (если он есть) — на любую, в том числе пустую, строку из плохих строчных латинских букв так, чтобы результат совпал со строкой.
В условии также даны буквы, считающиеся хорошими. Плохими являются все остальные буквы латинского алфавита.
Выходные данные
Выведите n строк: в i-й строке необходимо вывести «YES», если i-я строка-запрос удовлетворяет шаблону, и «NO» в противном случае.
Вы можете выводить каждую из букв в любом регистре.
Примечание
Объяснение первого теста. Символ «?» можно заменять на хорошие буквы «a» и «b», поэтому видно, что на первый запрос ответ «YES», а на второй запрос ответ «NO», потому что третья буква не может совпасть.
Объяснение второго теста.
- Первый запрос: «NO», потому что символ «*» можно заменять на строку из плохих букв, а единственный способ совпасть со строкой-запросом — заменить его на строку «ba», где оба символа — хорошие.
- Второй запрос: «YES», потому что «?» можно заменить на соответствующие хорошие буквы, а «*» — на пустую строку, и строки совпадут.
- Третий запрос: «NO», потому что «?» нельзя заменять на плохие буквы.
- Четвертый запрос: «YES», потому что «?» можно заменить на хорошие символы «a», а «*» — на строку из плохих букв «x».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ab
a?a
2
aaa
aab
|
YES
NO
|
|
2
|
abc
a?a?a*
4
abacaba
abaca
apapa
aaaaax
|
NO
YES
NO
YES
|