Statement is not available in English language
K. Приключения гуманоида 3
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

В точке $$$(0, 0)$$$ бесконечного клетчатого поля находится гуманоид, которым вы управляете. В точке $$$(n, m)$$$ находится горилла, которую вы хотите навестить. Горилла очень ждёт встречи с вами, но боится заблудиться, поэтому стоит на месте.

Для управления гуманоидом доступны четыре клавиши: $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$.

  • Клавиша $$$2$$$ перемещает гуманоида на одну клетку вверх $$$(x, y) \to (x, y + 1)$$$;
  • Клавиша $$$4$$$ перемещает гуманоида на одну клетку влево $$$(x, y) \to (x - 1, y)$$$;
  • Клавиша $$$6$$$ перемещает гуманоида на одну клетку вправо $$$(x, y) \to (x + 1, y)$$$;
  • Клавиша $$$8$$$ перемещает гуманоида на одну клетку вниз $$$(x, y) \to (x, y - 1)$$$.

Вам также приснилась строка $$$s$$$, задающая последовательность клавиш. Вы помните, что выбрали ровно $$$k$$$ последовательных клавиш из $$$s$$$ и нажали их по порядку. Мог ли гуманоид добраться до гориллы или вы что-то перепутали? Считается, что гуманоид добрался до гориллы, если ровно после $$$k$$$ шагов он закончил в клетке с ней.

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

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

Далее следуют описания наборов.

В первой строке записана строка $$$s$$$ ($$$s_i \in \{2, 4, 6, 8\}$$$, $$$1 \le |s| \le 10^6$$$) — последовательность клавиш.

Во второй строке даны целые числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$-10^6 \le n, m \le 10^6$$$, $$$1 \le k \le |s|$$$).

Гарантируется, что сумма длин $$$s$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Выведите «YES», если гуманоид мог добраться до гориллы и «NO» — в противном случае.

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

Пример
Входные данные
5
2846866484
-1 0 1
22268
-1 2 4
4
5 -3 1
26468228
2 -4 4
28844422
-3 -1 6
Выходные данные
YES
NO
NO
NO
YES