你正在处理电子游戏《Expansion Plan 2》中的支线任务。

存在一个由奖励关卡组成的无限网格，其坐标为 $(x, y)$（具体来说，$(0, 0)$ 正上方的单元格为 $(0, 1)$，$(0, 0)$ 正右方的单元格为 $(1, 0)$）。最初，只有位于 $(0, 0)$ 的奖励关卡是被解锁的。

给定一个长度为 $l$ 且由字符 "4" 和 "8" 组成的字符串 $a_1 a_2 \dots a_l$，你连续游玩 $l$ 次；在第 $i$ 次游玩中，你获得的分数等于 $s_i \in \{\text{"4"}, \text{"8"}\}$。对于从 $1$ 到 $l$ 的每个 $i$：

• 如果 $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 都会被识别为肯定回答）。

样例

输入样例 1

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

输出样例 1

YES
NO
YES
NO
YES
NO

说明

样例 1 说明。前三个询问的示意图如下：

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

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