CF1902D.Robot Queries

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

输入格式

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.

输出格式

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.

输入输出样例

输入#1

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

输出#1

YES
YES
NO

输入#2
```
4 2
RLDU
0 0 2 2
-1 -1 2 3
```
输出#2
```
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

输出#3

YES
YES
YES
NO
YES
YES

说明/提示

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:

首页