Приключения гуманоида 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» — в противном случае.

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

Пример

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

    52846866484-1 0 122268-1 2 445 -3 1264682282 -4 428844422-3 -1 6

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

    YES
    NO
    NO
    NO
    YES