刺猬 Daniyar 想要学习新的算法。为了帮助他的朋友，隐形人 Zhanadil 给 Daniyar 提供了 $N$ 本算法书，每本书都有其自身的重量 $w_i$ ($1 \le i \le N$)。刺猬 Daniyar 将这些书按 $1$ 到 $N$ 的顺序排列在书架上。

刺猬 Daniyar 的学习之旅持续 $M$ 天：在第 $i$ 天，他有兴趣阅读从 $l_i$ 到 $r_i$ 的书。作为一个完美主义者，他首先尝试将从 $l_i$ 到 $r_i$ 的书按重量非递减的顺序重新排列。为了实现这一点，只要两本相邻书的重量之和不超过他的心情值 $k_i$，刺猬就可以交换范围 $l_i$ 和 $r_i$ 内的任意两本相邻的书。幸运的是，他已经知道了未来 $M$ 天每一天的心情值。在每一天结束时，同样出于完美主义，他会将所有的书放回它们最初的位置。

请帮助刺猬改进他的计划——找出每一天他的心情值是否足以将书按重量非递减的顺序重新排列。

例如，假设刺猬 Daniyar 计划阅读三本书，当前排列为 $[3, 5, 4]$，他的心情值为 $8$。那么，很遗憾，这是不可能的，因为他无法交换重量为 $5$ 和 $4$ 的书（因为 $5 + 4 > 8$）。但如果他的心情值是 $9$，那么将书按重量非递减顺序重新排列就是可能的。

注意，每一天都是相互独立的，这意味着在每一天开始时，书的排列都会恢复到其初始状态。

输入格式

第一行包含两个整数 $N, M$ ($1 \le N, M \le 10^6$)，表示算法书的数量和天数。

第二行包含 $N$ 个整数 $w_1, w_2, \dots, w_N$ ($0 \le w_i \le 10^9$，对于所有 $1 \le i \le N$)，用空格分隔，表示每本书的重量。

接下来的 $M$ 行，每行包含三个整数 $l_i, r_i$ 和 $k_i$ ($1 \le l_i \le r_i \le N$ 且 $0 \le k_i \le 2 \cdot 10^9$)。刺猬 Daniyar 计划在特定的第 $i$ 天以心情值 $k_i$ 阅读从 $l_i$ 到 $r_i$ 的书。

输出格式

输出 $M$ 行，每行包含一个数字。如果刺猬 Daniyar 在第 $i$ 天能够阅读这些书，则第 $i$ 行应包含 $1$，否则包含 $0$。

子任务

本任务包含六个子任务：

1. $1 \le N, M \le 500$。分值为 $8$ 分。
2. $1 \le N, M \le 5000$。分值为 $9$ 分。
3. $1 \le N, M \le 10^6, 0 \le k < w_i$，其中 $1 \le i \le N$。分值为 $13$ 分。
4. $1 \le N, M \le 10^5, 0 \le w_i \le 1000$。分值为 $17$ 分。
5. $1 \le N, M \le 2 \cdot 10^5$。分值为 $30$ 分。
6. 满足上述题目描述中的约束条件。分值为 $23$ 分。

样例

输入 1

5 2
3 5 1 8 2
1 3 6
2 5 3

输出 1

1
0

说明

在第一个查询中，刺猬 Daniyar 可以通过以下方式实现正确的排列：

$[3, 5, 1, 8, 2]$ $[3, 1, 5, 8, 2]$ $[1, 3, 5, 8, 2]$