310869: CF1902D. Robot Queries

D. Robot Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is an infinite $2$-dimensional grid. Initially, a robot stands in the point $(0, 0)$. The robot can execute four commands:

• U — move from point $(x, y)$ to $(x, y + 1)$;
• D — move from point $(x, y)$ to $(x, y - 1)$;
• L — move from point $(x, y)$ to $(x - 1, y)$;
• R — move from point $(x, y)$ to $(x + 1, y)$.

You are given a sequence of commands $s$ of length $n$. Your task is to answer $q$ independent queries: given four integers $x$, $y$, $l$ and $r$; determine whether the robot visits the point $(x, y)$, while executing a sequence $s$, but the substring from $l$ to $r$ is reversed (i. e. the robot performs commands in order $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$).

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of the command sequence and the number of queries, respectively.

The second line contains a string $s$ of length $n$, consisting of characters U, D, L and/or R.

Then $q$ lines follow, the $i$-th of them contains four integers $x_i$, $y_i$, $l_i$ and $r_i$ ($-n \le x_i, y_i \le n$; $1 \le l \le r \le n$) describing the $i$-th query.

Output

For each query, print YES if the robot visits the point $(x, y)$, while executing a sequence $s$, but the substring from $l$ to $r$ is reversed; otherwise print NO.

ExamplesInput

8 3
RDLLUURU
-1 2 1 7
0 0 3 4
0 1 7 8

Output

YES
YES
NO

Input

4 2
RLDU
0 0 2 2
-1 -1 2 3

Output

YES
NO

Input

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

Output

YES
YES
YES
NO
YES
YES

Note

In the first query of the first sample, the path of the robot looks as follows:

In the second query of the first sample, the path of the robot looks as follows:

In the third query of the first sample, the path of the robot looks as follows:

题目大意：
在一个无限的二维网格中，有一个机器人初始位于点 (0, 0)。机器人可以执行四个命令：U（向上移动一格），D（向下移动一格），L（向左移动一格），R（向右移动一格）。给定一个长度为 n 的命令序列 s，机器人将按照这个序列移动。现在有 q 个独立查询，每个查询包含四个整数 x, y, l 和 r，需要判断在执行序列 s 的过程中，但子串从 l 到 r 反转的情况下（即命令顺序为 s_1 s_2 s_3 … s_{l-1} s_r s_{r-1} s_{r-2} … s_l s_{r+1} s_{r+2} … s_n），机器人是否会经过点 (x, y)。

输入输出数据格式：
输入：
- 第一行包含两个整数 n 和 q，分别表示命令序列的长度和查询的数量。
- 第二行包含一个长度为 n 的字符串 s，由字符 U、D、L 和 R 组成。
- 接下来 q 行，每行包含四个整数 x_i, y_i, l_i 和 r_i，描述一个查询。

输出：
- 对于每个查询，如果机器人会经过点 (x, y)，则输出 YES，否则输出 NO。

LaTeX 格式的公式：
题目中没有提供需要用 LaTeX 格式表示的公式。题目大意： 在一个无限的二维网格中，有一个机器人初始位于点 (0, 0)。机器人可以执行四个命令：U（向上移动一格），D（向下移动一格），L（向左移动一格），R（向右移动一格）。给定一个长度为 n 的命令序列 s，机器人将按照这个序列移动。现在有 q 个独立查询，每个查询包含四个整数 x, y, l 和 r，需要判断在执行序列 s 的过程中，但子串从 l 到 r 反转的情况下（即命令顺序为 s_1 s_2 s_3 … s_{l-1} s_r s_{r-1} s_{r-2} … s_l s_{r+1} s_{r+2} … s_n），机器人是否会经过点 (x, y)。 输入输出数据格式： 输入： - 第一行包含两个整数 n 和 q，分别表示命令序列的长度和查询的数量。 - 第二行包含一个长度为 n 的字符串 s，由字符 U、D、L 和 R 组成。 - 接下来 q 行，每行包含四个整数 x_i, y_i, l_i 和 r_i，描述一个查询。 输出： - 对于每个查询，如果机器人会经过点 (x, y)，则输出 YES，否则输出 NO。 LaTeX 格式的公式： 题目中没有提供需要用 LaTeX 格式表示的公式。