← 返回题目列表

Codeforces · 1599/F

F. 火星

中文机器翻译题面 查看原题

在埃隆·图斯克的努力下,2420 年人类终于在火星上建立了殖民地。该殖民地有 $$$10^9+7$$$ 城市排列成一圈,但尚未连接。埃隆·图斯克希望仅使用相同规模的道路连接其中一些城市,以降低这些道路的生产成本。因此,他给出了 N 个引用的列表,其中一些引用可能出现多次,以及您需要回答的 Q 个查询。对于该查询,您需要确定是否可以仅使用长度为 $$$D_{i}$$$ 的道路连接该列表中从 $$$L_{i}$$$ 到 $$$R_{i}$$$ 的所有城市。

输入

第一行包含两个整数 $$$N$$$ 和 $$$Q$$$ ($$$1 \leq N, Q \leq 2\cdot10^5$$$ ) — 城市数组的长度和需要回答的查询数量。

第二行包含表示引用数组的 $$$N$$$ 整数。接下来的 Q 行包含三个整数 $$$L、R$$$ 和 $$$D$$$ ($$$1 \leq L_{i}, R_{i} \leq N$$$, $$$0 \leq D_{i} \leq 10^9+6$$$) — 需要连接的城市范围和可以使用的道路长度。

输出

输出包含 Q 行。如果可以连接第 i 个查询中的所有城市可以与长度为 $$$D_{i}$$$ 的道路连接,则第 i 行应包含单词“Yes”,否则应包含单词“No”。

示例

输入 #1

9 8
17 0 12 6 10 8 2 4 5
2 3 12
2 3 6
2 4 6
4 6 2
2 8 2
1 2 17
1 8 2
9 9 14

输出 #1

Yes
No
Yes
Yes
Yes
Yes
No
Yes

输入 #2

4 1
7 21 14 0
1 4 1000000000

输出 #2

Yes

注意

在第一个测试用例的 $$$5^{th}$$$ 查询中,我们可以按 0-2-4-6-8-10-12 的顺序连接城市,这样任意两个连接的城市之间的距离为 2。在第二个测试用例中,我们可以按 21-14-7-0 的顺序连接城市,这样任意两个连接的城市之间的距离为 $$$10^9$$$ module $$$10^9+7$$$。