B. Петя и ЕГЭ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Настали тяжелые времена. Сегодня Пете нужно набрать на экзамене по информатике 100 баллов. Все задачи на экзамене Пете кажутся простыми, но он боится, что не успеет сделать одну из них за такой маленький промежуток времени, поэтому он обратился к вам за помощью.

В условии даётся шаблон (строка, состоящая из строчных латинских букв, символов «?» и «*»). Известно, что символ «*» встречается в шаблоне не более одного раза.

Также в условии даны n строк-запросов, и для каждой необходимо определить, подходит ли она под данный шаблон, или нет.

Все было бы хорошо, но специальные символы в шаблоне в этой задаче действуют не так, как обычно!

Строка подходит под шаблон, если можно в шаблоне заменить каждый из символов «?» на одну хорошую строчную латинскую букву, а символ «*» (если он есть) — на любую, в том числе пустую, строку из плохих строчных латинских букв так, чтобы результат совпал со строкой.

В условии также даны буквы, считающиеся хорошими. Плохими являются все остальные буквы латинского алфавита.

Входные данные

В первой строке находится строка, содержащая от 1 до 26 различных строчных латинских букв. Это буквы, которые считаются в задаче хорошими. Все остальные буквы — плохие.

Во второй строке находится шаблон — строка s из строчных букв латинского алфавита, символов «?» и «*» (1 ≤ |s| ≤ 105). Гарантируется, что символ «*» встречается в s не более одного раза.

Во третьей строке находится целое число n (1 ≤ n ≤ 105) — количество строк-запросов.

Далее следуют n строк, в каждой из них находится по одной непустой строке, состоящей из строчных латинских букв — очередная строка-запрос.

Гарантируется, что сумма длин всех строк-запросов не превосходит 105.

Выходные данные

Выведите n строк: в i-й строке необходимо вывести «YES», если i-я строка-запрос удовлетворяет шаблону, и «NO» в противном случае.

Вы можете выводить каждую из букв в любом регистре.

Примеры
Входные данные
ab
a?a
2
aaa
aab
Выходные данные
YES
NO
Входные данные
abc
a?a?a*
4
abacaba
abaca
apapa
aaaaax
Выходные данные
NO
YES
NO
YES
Примечание

Объяснение первого теста. Символ «?» можно заменять на хорошие буквы «a» и «b», поэтому видно, что на первый запрос ответ «YES», а на второй запрос ответ «NO», потому что третья буква не может совпасть.

Объяснение второго теста.

  • Первый запрос: «NO», потому что символ «*» можно заменять на строку из плохих букв, а единственный способ совпасть со строкой-запросом — заменить его на строку «ba», где оба символа — хорошие.
  • Второй запрос: «YES», потому что «?» можно заменить на соответствующие хорошие буквы, а «*» — на пустую строку, и строки совпадут.
  • Третий запрос: «NO», потому что «?» нельзя заменять на плохие буквы.
  • Четвертый запрос: «YES», потому что «?» можно заменить на хорошие символы «a», а «*» — на строку из плохих букв «x».