Задача №114781. Загадочное устройство
У Димы есть устройство, содержащее \(n + m\) кнопок и экран. На экране отображается строка \(s\), изначально она пустая. Если нажать на кнопку с номером \(i\) (\(1 \le i \le n\)), то в конец строки \(s\) допишется строка \(w_i\). Если нажать на кнопку с номером \(n + i\) (\(1 \le i \le m\)), то из конца строки \(s\) удалится \(a_i\) символов. Если в строке \(s\) было меньше \(a_i\) символов, она станет пустой.
У Димы есть \(q\) любимых строк \(t_i\). Для каждой из них он хочет узнать, можно ли в результате нескольких нажатий на кнопки из пустой строки \(s\) сделать строку равную \(t_i\).
В первой строке дано два целых числа \(n\) и \(m\) — количество кнопок первого и второго типа (\(1 \le n, m \le 100\,000\)).
В следующих \(n\) строках даны непустые строки \(w_i\), состоящие из строчных английских букв. Сумма длин всех строк \(w_i\) не превышает \(10^6\).
В следующих \(m\) строках даны числа \(a_i\) (\(1 \le a_i \le 10^6\)).
В следующей строке дано целое число \(q\) — количество любимых строк Димы (\(1 \le q \le 100\,000\)).
В следующих \(q\) строках даны непустые строки \(t_i\), состоящие из строчных английских букв. Сумма длин всех строк \(t_i\) не превышает \(10^6\).
Для каждой строки \(t_i\) в новой строке выведите « Yes », если можно \(s\) сделать равным \(t_i\), и « No » иначе.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 12 | \(\sum |w_i| \le 1\,000\), \(\sum |t_i| \le 1\,000\), \(m = 1\), \(|w_i| = a_1\) | первая ошибка | |
| 2 | 13 | \(\sum |w_i| \le 1\,000\), \(\sum |t_i| \le 1\,000\), \(m = 1\), \(a_1 = 1\) | первая ошибка | |
| 3 | 19 | \(\sum |w_i| \le 1\,000\), \(\sum |t_i| \le 1\,000\) | 1 | первая ошибка |
| 4 | 29 | \(\sum |w_i| \le 100\,000\), \(\sum |t_i| \le 100\,000\) | 1, 2 | первая ошибка |
| 5 | 27 | Без дополнительных ограничений | 1–3 | первая ошибка |
2 1 bba abacaba 2 4 b ababbab abacabba caba
Yes Yes Yes No