В точке $$$(0, 0)$$$ $$$2$$$-мерной плоскости стоит робот. Робот может выполнять четыре команды:
- U — переместиться из точки $$$(x, y)$$$ в $$$(x, y + 1)$$$;
- D — переместиться из точки $$$(x, y)$$$ в $$$(x, y - 1)$$$;
- L — переместиться из точки $$$(x, y)$$$ в $$$(x - 1, y)$$$;
- R — переместиться из точки $$$(x, y)$$$ в $$$(x + 1, y)$$$.
Задана последовательность команд $$$s$$$ длины $$$n$$$. Ваша задача — ответить на $$$q$$$ независимых запросов: для четырех целых чисел $$$x$$$, $$$y$$$, $$$l$$$ и $$$r$$$ определить, посетит ли робот точку $$$(x, y)$$$, выполняя последовательность $$$s$$$, где подстрока с $$$l$$$ по $$$r$$$ перевернута (то есть робот выполняет команды в порядке $$$s_1 s_2 s_3 \dots s_{l-1} s_r s_{r-1} s_{r-2} \dots s_l s_{r+1} s_{r+2} \dots s_n$$$).
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — длину последовательности команд и количество запросов соответственно.
Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов U, D, L и/или R.
Затем следуют $$$q$$$ строк, $$$i$$$-я из них содержит четыре целых числа $$$x_i$$$, $$$y_i$$$, $$$l_i$$$ и $$$r_i$$$ ($$$-n \le x_i, y_i \le n$$$; $$$1 \le l \le r \le n$$$), описывающие $$$i$$$-й запрос.
Для каждого запроса выведите YES, если робот посещает точку $$$(x, y)$$$, выполняя последовательность $$$s$$$, где подстрока с $$$l$$$ по $$$r$$$ перевернута; в противном случае выведите NO.
8 3RDLLUURU-1 2 1 70 0 3 40 1 7 8
YES YES NO
4 2RLDU0 0 2 2-1 -1 2 3
YES NO
10 6DLUDLRULLD-1 0 1 10-1 -2 2 5-4 -2 6 10-1 0 3 90 1 4 7-3 -1 5 8
YES YES YES NO YES YES
В первом запросе первого примера путь робота выглядит следующим образом:
Во втором запросе первого примера путь робота выглядит следующим образом:
В третьем запросе первого примера путь робота выглядит следующим образом:
