← 返回题目列表

Codeforces · 1902/D

D. 机器人查询

中文机器翻译题面 查看原题

有一个无限的 $$$2$$$ 维网格。最初,机器人站在 $$$(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$$$;确定机器人是否访问点 $$$(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} \点 s_n$$$)。

输入

第一行包含两个整数 $$$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$$$ 个查询。

输出

对于每个查询,如果机器人在执行序列 $$$s$$$ 时访问点 $$$(x, y)$$$,但从 $$$l$$$ 到 $$$r$$$ 的子串被反转,则打印 YES;否则打印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

注意

在第一个样本的第一个查询中,机器人的路径如下所示:

在第一个样本的第二个查询中,机器人的路径如下所示:

在第一个样本的第三个查询中,机器人的路径如下所示: