← К соревнованиям

Индивидуальная олимпиада по информатике и программированию

Загадочное устройство

Сложность: 70%

У Димы есть устройство, содержащее n+mn + m кнопок и экран. На экране отображается строка ss, изначально она пустая. Если нажать на кнопку с номером ii (1in1 \le i \le n), то в конец строки ss допишется строка wiw_i. Если нажать на кнопку с номером n+in + i (1im1 \le i \le m), то из конца строки ss удалится aia_i символов. Если в строке ss было меньше aia_i символов, она станет пустой.

У Димы есть qq любимых строк tit_i. Для каждой из них он хочет узнать, можно ли в результате нескольких нажатий на кнопки из пустой строки ss сделать строку равную tit_i.

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

В первой строке дано два целых числа nn и mm – количество кнопок первого и второго типа (1n,m1000001 \le n, m \le 100\,000).

В следующих nn строках даны непустые строки wiw_i, состоящие из строчных английских букв. Сумма длин всех строк wiw_i не превышает 10610^6.

В следующих mm строках даны числа aia_i (1ai1061 \le a_i \le 10^6).

В следующей строке дано целое число qq – количество любимых строк Димы (1q1000001 \le q \le 100\,000).

В следующих qq строках даны непустые строки tit_i, состоящие из строчных английских букв. Сумма длин всех строк tit_i не превышает 10610^6.

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

Для каждой строки tit_i в новой строке выведите Yes, если можно ss сделать равным tit_i, и No иначе.

Подзадачи

баллынеобх. подзадачиограничения
1

12

-

wi1000\sum |w_i| \le 1\,000, ti1000\sum |t_i| \le 1\,000, m=1m = 1, wi=a1|w_i| = a_1

2

13

-

wi1000\sum |w_i| \le 1\,000, ti1000\sum |t_i| \le 1\,000, m=1m = 1, a1=1a_1 = 1

3

19

1

wi1000\sum |w_i| \le 1\,000, ti1000\sum |t_i| \le 1\,000

4

29

1, 2

wi100000\sum |w_i| \le 100\,000, ti100000\sum |t_i| \le 100\,000

5

27

1, 2, 3

Нет дополнительных ограничений

STDINSTDOUT
2 1
bba
abacaba
2
4
b
ababbab
abacabba
caba
Yes
Yes
Yes
No