C. Сильный пароль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп наконец-то набрался смелости зарегистрироваться на ForceCoders. Он придумал ник, но все еще думает насчет пароля.

Он хочет, чтобы пароль был как можно сильнее, поэтому придумал следующие критерии:

  • длина пароля должна быть ровно $$$m$$$;
  • пароль должен состоять только из цифр от $$$0$$$ до $$$9$$$;
  • пароль не должен встречаться в базе данных паролей (заданной строкой $$$s$$$) как подпоследовательность (не обязательно подряд идущих цифр).

Монокарп также придумал две строки длины $$$m$$$: $$$l$$$ и $$$r$$$, обе состоящие только из цифр от $$$0$$$ до $$$9$$$. Он хочет, чтобы $$$i$$$-я цифра его пароля была от $$$l_i$$$ до $$$r_i$$$ включительно.

Существует ли пароль, который подходит под все условия?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записана строка $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), состоящая только из цифр от $$$0$$$ до $$$9$$$ — база данных паролей.

Во второй строке записано одно целое число $$$m$$$ ($$$1 \le m \le 10$$$) — требуемая длина пароля.

В третьей строке записана строка $$$l$$$ ($$$|l| = m$$$), состоящая только из цифр от $$$0$$$ до $$$9$$$, — нижняя граница на каждую цифру.

В четвертой строке записана строка $$$r$$$ ($$$|r| = m$$$), состоящая только из цифр от $$$0$$$ до $$$9$$$, — верхняя граница на каждую цифру. $$$l_i \le r_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$m$$$.

Сумма длин $$$s$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

На каждый набор входных данных выведите «YES», если существует пароль, который подходит под все условия. Иначе выведите «NO».

Пример
Входные данные
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11
Выходные данные
YES
NO
YES
NO
YES
Примечание

В первом наборе входных данных Монокарп может выбрать пароль «50». Он не встречается в $$$s$$$ как подпоследовательность.

Во втором наборе все наборы из трех цифр, каждая из которых от $$$1$$$ до $$$4$$$, подходит под условия на $$$l$$$ и $$$r$$$. Однако, все они встречаются в $$$s$$$ как подпоследовательности. Например, «314» встречается на позициях $$$[3, 5, 12]$$$, а «222» встречается на позициях $$$[2, 6, 10]$$$.

В третьем наборе Монокарп может выбрать пароль «4321». На самом деле это единственный пароль, который подходит под условия на $$$l$$$ и $$$r$$$. К счастью, он не встречается в $$$s$$$ как подпоследовательность.

В четвертом наборе только «49» и «59» подходят под условия на $$$l$$$ и $$$r$$$. Оба они встречаются в $$$s$$$ как подпоследовательности.

В пятом набор Монокарп может выбрать пароль «11».