说明

你正在处理电子游戏 扩张计划 2 中的支线任务。

有一个无限的奖励关卡网格，坐标为 $(x, y)$（具体来说，$(0,0)$ 正上方的格子是 $(0,1)$，$(0,0)$ 正右方的格子是 $(1,0)$）。初始时，只有位于 $(0,0)$ 的奖励关卡处于解锁状态。

给定一个长度为 $l$、由字符“4”和“8”组成的字符串 $a_1a_2 \dots a_l$，你连续进行 $l$ 次游戏；在第 $i$ 次游戏中，你获得一个分数 $s_i \in \{"4", "8"\}$。对于每个 $i$ 从 $1$ 到 $l$：

• 如果 $s_i = \text{"4"}$：对于每个奖励关卡，如果它在第 $i$ 次游戏之前与一个已经解锁的关卡正交相邻（即共享一条边），则该关卡变为解锁；否则，其状态保持不变；
• 如果 $s_i = \text{"8"}$：对于每个奖励关卡，如果它在第 $i$ 次游戏之前与一个已经解锁的关卡正交或对角相邻（即共享一条边或一个角），则该关卡变为解锁；否则，其状态保持不变。

给定一个长度为 $n$、由字符“4”和“8”组成的字符串 $s$。

你需要回答 $q$ 个查询。在每个查询中，你从一个只有奖励关卡 $(0,0)$ 解锁的无限网格开始，并给定四个整数 $l, r, x, y$。你需要判断在获得 $s$ 的子串 $[l, r]$ 中的分数后，奖励关卡 $(x,y)$ 是否被解锁。

输入格式

第一行包含两个整数 $n, q$（$1 \le n, q \le 2 \cdot 10^5$）—— 分别表示字符串的长度和查询的数量。

第二行包含一个长度为 $n$、由字符“4”和“8”组成的字符串 $s$。

接下来的 $q$ 行，每行包含四个整数 $l, r, x, y$（$1 \le l \le r \le n$，$-10^9 \le x, y \le 10^9$），表示对子串 $[l, r]$ 和奖励关卡 $(x, y)$ 的查询。

输出格式

对于每个查询，如果奖励关卡 $(x, y)$ 在获得 $s$ 的子串 $[l, r]$ 中的分数后解锁，则输出 YES，否则输出 NO。

评测系统对大小写不敏感（例如，YES、Yes、yes、yEs 都会被识别为肯定答案）。

10 6
4884884888
8 10 3 3
4 7 5 1
4 7 3 -3
1 7 -7 -5
1 10 0 0
1 1 1 1

YES
NO
YES
NO
YES
NO

提示

样例解释

前三个查询的示意图如下：

:::align{center} :::

在第一个查询中，$[l, r] = [8, 10]$，且 $(x, y) = (3, 3)$。$s$ 的子串 $[8, 10]$ 是“888”。在获得该子串中的分数后，奖励关卡 $(3, 3)$ 被解锁，因此答案为 YES。

在第二个查询中，奖励关卡 $(5, 1)$ 在获得子串“4884”中的分数后并未解锁。

翻译由 DeepSeek 完成