В точке \((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\)).
Выходные данные
Для каждого запроса выведите YES, если робот посещает точку \((x, y)\), выполняя последовательность \(s\), где подстрока с \(l\) по \(r\) перевернута; в противном случае выведите NO.
Примечание
В первом запросе первого примера путь робота выглядит следующим образом:
Во втором запросе первого примера путь робота выглядит следующим образом:
В третьем запросе первого примера путь робота выглядит следующим образом:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 3
RDLLUURU
-1 2 1 7
0 0 3 4
0 1 7 8
|
YES
YES
NO
|
|
2
|
4 2
RLDU
0 0 2 2
-1 -1 2 3
|
YES
NO
|
|
3
|
10 6
DLUDLRULLD
-1 0 1 10
-1 -2 2 5
-4 -2 6 10
-1 0 3 9
0 1 4 7
-3 -1 5 8
|
YES
YES
YES
NO
YES
YES
|