B. План расширения 2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
ak+q - over the crimson skies
⠀

Вы анализируете бесконечную сетку, на которой введены координаты $$$(X, Y)$$$ (в частности, ячейка, находящаяся над $$$(0, 0)$$$ — это $$$(0, 1)$$$, а ячейка, находящаяся справа от $$$(0, 0)$$$ — это $$$(1, 0)$$$). Изначально только ячейка $$$(0, 0)$$$ черная.

Вам дана строка $$$a_1a_2 \ldots a_n$$$ длиной $$$n$$$, состоящая из символов $$$\texttt{"4"}$$$ и $$$\texttt{"8"}$$$, которая описывает $$$n$$$ операций расширения. На каждом шаге $$$i$$$ от $$$1$$$ до $$$n$$$ следующее происходит одновременно для всех ячеек:

  • если $$$s_i = \texttt{"4"}$$$: для каждой ячейки, если она соседствует с чёрной ячейкой по стороне, она становится чёрной; в противном случае её состояние остаётся прежним;
  • если $$$s_i = \texttt{"8"}$$$: для каждой ячейки, если она соседствует с чёрной ячейкой по стороне или по диагонали (т.е. она делит сторону или угол), она становится черной; в противном случае её состояние остается прежним.

Является ли ячейка $$$(x, y)$$$ черной в конце процесса?

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$x$$$, $$$y$$$ ($$$1 \le n \le 2 \cdot 10^5, -10^9 \le x, y \le 10^9$$$) — количество операций расширения и координаты $$$x$$$ и $$$y$$$ ячейки, которая вас интересует.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длиной $$$n$$$, состоящую из символов $$$\texttt{"4"}$$$ и $$$\texttt{"8"}$$$ — типы операций расширения.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$\texttt{YES}$$$, если ячейка $$$(x, y)$$$ является чёрной после операций расширения, описанных строкой $$$s$$$, и $$$\texttt{NO}$$$ в противном случае.

Вы можете выводить каждую букву в любом регистре (например, $$$\texttt{YES}$$$, $$$\texttt{Yes}$$$, $$$\texttt{yes}$$$, $$$\texttt{yEs}$$$ будут приняты как положительный ответ).

Пример
Входные данные
6
3 3 3
888
4 5 1
4884
4 3 -3
4884
7 -7 -5
4884884
10 0 0
4884884888
1 1 1
4
Выходные данные
YES
NO
YES
NO
YES
NO
Примечание

Первые три набора входных данных проиллюстрированы ниже:

В первом наборе входных данных, после операций расширения, описанных строкой $$$\texttt{"888"}$$$, ячейка $$$(3, 3)$$$ чёрная, поэтому ответ — $$$\texttt{YES}$$$.

Во втором наборе входных данных ячейка $$$(5, 1)$$$ белая после операций расширения, описанных строкой $$$\texttt{"4884"}$$$.