题目描述

题目译自 JOI 2024 Final T3 「マラソン大会 2 / Marathon Race 2」

JOI 大道是一条东西向的长度为 $L$ 米的道路，地点 $l$ 位于从道路的西端走 $l$（$0 \leq l \leq L$）米的地方。

今年 JOI 大道上第一次举办了马拉松大会。这个马拉松大会的规则和一般的不同，是按照以下的方式进行的：

1. 道路上放了 $N$ 个球，第 $i$（$1 \leq i \leq N$）个球放在地点 $X_i$。有些地方可能有多个球放在一起。
2. 参加者从规定的起点出发。
3. 拿到所有 $N$ 个球后，如果在规定的时间内到达规定的终点，就算是完赛。但是，如果把拿到的球放在地上就会被取消资格。

这个大会的起点，终点和时间限制还没有公布，但是已经公布了 $Q$ 个可能的方案。第 $j$（$1 \leq j \leq Q$）个方案的起点是地点 $S_j$，终点是地点 $G_j$，时间限制是 $T_j$ 秒。

理恵是马拉松大会的其中一名运动员。她拿起一个球要花 $1$ 秒，拿着 $x$ 个球在道路上跑 $1$ 米要花 $x+1$ 秒。

给出 JOI 大道，球，方案的信息。编写一个程序，对于每个方案判断理恵能不能完赛。

输入格式

第一行包含两个整数 $N$,$L$。

第二行包含用空格分隔的 $N$ 个整数 $X_1, X_2, \ldots ,X_N$。

第三行包含一个整数 $Q$。

接下来 $Q$ 行，每行包含三个整数 $S_j, G_j, T_j$，表示第 $j$ 个方案。

输出格式

输出 $Q$ 行。第 $j$（$1 \leq j \leq Q$）行，如果第 $j$ 个方案理恵能完赛输出 Yes，否则输出 No。

样例 1

输入

$3$ $100$ $30$ $80$ $30$ $3$ $0$ $100$ $403$ $0$ $100$ $300$ $0$ $100$ $262$

输出

Yes Yes No

说明

第一个方案的起点是地点 $0$，终点是地点 $100$，时间限制是 $403$ 秒。按照以下的方式，可以在 $263$ 秒内完赛。所以第一行输出 Yes。

顺序	行动	花费时间	累计时间
$1$	从地点 $0$ 出发，到地点 $30$。	$30$ 秒
$2$	拿第一个球。	$1$ 秒	$31$ 秒
$3$	拿第三个球。		$32$ 秒
$4$	从地点 $30$ 到地点 $80$。	$150$ 秒	$182$ 秒
$5$	拿第二个球。	$1$ 秒	$183$ 秒
$6$	从地点 $80$ 到地点 $100$，完赛。	$80$ 秒	$263$ 秒

第二个方案的起点和终点和第一个方案一样，但是时间限制是 $300$ 秒。用前面的方法，可以在 $263$ 秒内完赛。所以，第二行输出 Yes。

第三个方案的起点和终点和前面两个方案一样，但是时间限制是 $262$ 秒。不能在时间限制内完赛。所以，第三行输出 No。

这个样例满足子任务 $2,3,4,5,6,7$ 的限制。

样例 2

输入

$3$ $100$ $30$ $80$ $30$ $3$ $0$ $0$ $403$ $0$ $0$ $300$ $0$ $0$ $262$

输出

Yes No No

说明

第一个方案的起点是地点 $0$，终点也是地点 $0$，时间限制是 $403$ 秒。按照以下的方式，可以在 $403$ 秒内完赛。所以，第一行输出 Yes。

顺序	行动	花费时间	累计时间
$1$	从地点 $0$ 出发，到地点 $30$。	$30$ 秒
$2$	拿第一个球。	$1$ 秒	$31$ 秒
$3$	从地点 $30$ 到地点 $80$。	$100$ 秒	$131$ 秒
$4$	拿第二个球。	$1$ 秒	$132$ 秒
$5$	从地点 $80$ 到地点 $30$。	$150$ 秒	$282$ 秒
$6$	拿第三个球。	$1$ 秒	$283$ 秒
$7$	从地点 $30$ 到地点 $0$，完赛。	$120$ 秒	$403$ 秒

第二个方案和第三个方案的起点和终点和第一个方案一样，但是时间限制分别是 $300$ 秒和 $262$ 秒。都不能在时间限制内完赛。所以，第二行和第三行都输出 No。

这个样例满足子任务 $1,2,3,4,5,6,7$ 的限制。

样例 3

输入

$6$ $100$ $0$ $50$ $100$ $0$ $50$ $100$ $4$ $20$ $70$ $600$ $70$ $20$ $600$ $10$ $40$ $600$ $40$ $10$ $600$

输出

No Yes No Yes

这个样例满足子任务 $2,3,4,5,6,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 5\times 10^5$
• $1 \leq L \leq 5\times 10^5$
• $0 \leq X_i \leq L$（$1 \leq i \leq N$）
• $1 \leq Q \leq 5\times 10^5$
• $0 \leq S_j \leq L$（$1 \leq j \leq Q$）
• $0 \leq G_j \leq L$（$1 \leq j \leq Q$）
• $1 \leq T_j \leq 5\times 10^5$（$1 \leq j \leq Q$）

详细子任务附加限制及分值如下表所示：

子任务	附加限制	分值
$1$	$N \leq 7$，$Q \leq 10$，$S_j=0$，$G_j=0$（$1 \leq j \leq Q$）	$7$
$2$	$N \leq 7$，$Q \leq 10$
$3$	$N \leq 14$，$Q \leq 10$	$10$
$4$	$N \leq 100$，$Q \leq 10$	$28$
$5$	$N \leq 2000$，$Q \leq 10$	$10$
$6$	$N \leq 2000$	$19$
$7$	无附加限制