Mars

题意翻译

## 题目描述 在2420年，人类成功在火星上建立了第一个殖民地。现在，这个殖民地里含有 $N$ 个城市，第 $i$ 个城市相对于零点的距离为 $N_i$，但是，现在这些城市还没有联通，所以需要用道路来联通它们。现在，设计道路的工程师找到了你，希望你来帮助他设计道路。 设计师会给你 $Q$ 组询问，每个询问包含三个整数：需要连接的城市的区间 $L$ 与 $R$ 与使用的道路长度 $D$ 。设计师想要用这个长度为 $D$ 的道路连接 $L$ 到 $R$ 之间的所有城市，使它们在连接后两两可以到达，但是每两个城市之间，最多建设$1$条这种道路。——如你所见，这很有可能导致无法连通其中一些城市。现在，设计师想问问你，按照他的方案，能否将区间内所有城市连通。 两个城市能连通，当道路长度大于等于其之间的距离。 ## 输入格式 第一行包含两个整数， $N$ 与 $Q(1\leqslant N,Q \leqslant 2*10^5)$——城市的个数与询问组数。 接下来的一行会输入 $N$ 个整数，表示城市的位置。 接下来的 $Q$ 行包含三个整数，$L$ , $R$ ,和 $D$ $(1 \leqslant L_i,R_i \leqslant N,0\leqslant D_i\leqslant 10^9+6)$ ——区间的起点与终点，使用的道路长度。 ## 输出格式 输出包含 $Q$ 行。对于每一个询问，如果能用这种道路连通所有城市，那么输出 "Yes" ,否则输出 "No"。 ## 样例解释 对于第一组数据中的第五个询问，设计师想用长度为$2$的道路连接2号城市到8号城市。他可以按照如下顺序来连接：2号-7号-8号-4号-6号-5号-3号（对应的城市坐标为0-2-4-8-10-12）,使被连接的城市都可用长度2的道路连接。 对于第二组数据，设计师无论怎么连，都可以用长度为 $10^9$ 的道路连接任意两个城市。

题目描述

In the year 2420 humans have finally built a colony on Mars thanks to the work of Elon Tusk. There are $ 10^9+7 $ cities arranged in a circle in this colony and none of them are connected yet. Elon Tusk wants to connect some of those cities using only roads of the same size in order to lower the production cost of those roads. Because of that he gave a list on N cites where some cites can appear more than once and Q queries that you need to answer. For the query you need to determine if it is possible to connect all the cities from $ L_{i} $ to $ R_{i} $ on that list using only roads of length $ D_{i} $ .

输入输出格式

输入格式

The first line contains two integers $ N $ and $ Q $ ( $ 1 \leq N, Q \leq 2\cdot10^5 $ ) — the length of the array of cities and the number of queries you need to answer. The second lines contains $ N $ integers representing the array of cites. Next Q lines contain three integers $ L, R $ and $ D $ ( $ 1 \leq L_{i}, R_{i} \leq N $ , $ 0 \leq D_{i} \leq 10^9+6 $ ) — the range of cities that needs to be connected and the length of the road that you can use.

输出格式

The output contains Q lines. If it is possible to connect all the cities from the i-th query can be connected with roads of length $ D_{i} $ the i-th line should contain the word "Yes", otherwise it should contain the word "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

说明

In the $ 5^{th} $ query of the first test case we can connect cities in this order 0-2-4-6-8-10-12 this way distance between any two connected cities is 2. In the second test case we can connect cities in this order 21-14-7-0 this way distance between any two connected cities is $ 10^9 $ module $ 10^9+7 $ .