CF1902D.Robot Queries

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$).

存在一个无限大的二维网格。初始时，机器人位于点 $(0, 0)$。机器人可以执行以下四种指令：

• U — 从点 $(x, y)$ 移动到 $(x, y + 1)$；
• D — 从点 $(x, y)$ 移动到 $(x, y - 1)$；
• L — 从点 $(x, y)$ 移动到 $(x - 1, y)$；
• R — 从点 $(x, y)$ 移动到 $(x + 1, y)$。

给定一个长度为 $n$ 的指令序列 $s$。你需要回答 $q$ 个相互独立的询问：每次询问给出四个整数 $x$、$y$、$l$ 和 $r$；判断机器人在执行序列 $s$ 的过程中（但将子串 $s[l..r]$ 反转）是否会访问点 $(x, y)$（即机器人执行的指令序列为 $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$）。

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.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$），分别表示指令序列的长度和查询次数。

第二行包含一个长度为 $n$ 的字符串 $s$，由字符 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$ 个查询。

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.

对于每个查询，如果机器人在执行序列 $s$ 时访问了点 $(x, y)$，但子串 $s[l..r]$ 被反转，则输出 YES；否则输出 NO。

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:

在第一个样例的第一个查询中，机器人的路径如下所示：

在第一个样例的第二个查询中，机器人的路径如下所示：

在第一个样例的第三个查询中，机器人的路径如下所示：