题目描述

在一个无限大的二维平面上，一具产生了自我意识的战斗型机器人于 $(0,0)$ 处苏醒。在 $q$ 个互相独立互不影响的平行时空内，它开始按字符串指令 $S$ 执行移动。但由于故障，它忽视了指令中 $[l,r]$ 这一段指令。

对于这 $q$ 个时空，每个时空都为故障机器人安排了一个遗物位于点 $(x,y)$。你需要判断机器人是否能够经过这个点。

问题形式化

给定整数 $n$, $q$ 和字符串 $S$。$n$ 为字符串长度，$q$ 为询问次数，$S$ 为移动指令字符串，只包含 L、R、U 和 D 四种字符，移动规则如下：

• L：从 $(x,y)$ 移动到 $(x-1,y)$
• R：从 $(x,y)$ 移动到 $(x+1,y)$
• U：从 $(x,y)$ 移动到 $(x,y+1)$
• D：从 $(x,y)$ 移动到 $(x,y-1)$

每次独立询问给出四个整数 $l, r, x, y$，表示 $[S_l, S_{l+1}, \ldots, S_{r-1}, S_r]$ 这段指令不会被执行。如果这种情况下机器人能经过点 $(x,y)$，输出 YES，否则输出 NO。

注意： 本题输入输出量较大，请使用快速的输入输出方式。

输入格式

第一行输入两个整数 $n$, $q$ ($1 \leq n \leq 5 \times 10^5$, $1 \leq q \leq 5 \times 10^5$)。

接下来输入一行一个长度为 $n$ 的字符串 $S$，保证只包含 L、R、U 和 D 四种字符。

接下来 $q$ 行，每行输入四个整数 $l$, $r$, $x$, $y$ ($1 \leq l \leq r \leq n$, $-10^9 \leq x, y \leq 10^9$)。含义如题意所示。

输出格式

输出 $q$ 行，对于每个询问，输出一行一个 YES 或者 NO（不含引号）。

输出对大小写不敏感。例如，YES 与 yEs 都可以表示机器人能经过该点。

样例

4 3
LURD
1 1 -1 0
1 1 1 0
2 2 -1 -1

NO
YES
NO