有一个无限的 $$$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
注意
在第一个样本的第一个查询中,机器人的路径如下所示:
在第一个样本的第二个查询中,机器人的路径如下所示:
在第一个样本的第三个查询中,机器人的路径如下所示: