AT_joi2024ho_c.マラソン大会 2 (Marathon Race 2)

JOI 街道是一条东西方向延伸、长为 $L$ 米的道路。从道路西端起第 $l$ 米处称为地点 $l$。

今年，JOI 街道将首次举办马拉松比赛。与普通马拉松不同，本次比赛有如下规则：

• 道路上放置了 $N$ 个球，第 $i$ 个球（$1 \leq i \leq N$）放在地点 $X_i$。多个球可能位于同一地点。
• 参赛者从指定的起点出发。
• 只有在到达指定的终点，并且收集了全部 $N$ 个球，并在限定时间内到达，才能算作完赛。但如果在持有球的情况下将球放下，则会被判定为失格。

本次比赛的起点、终点和限制时间尚未公布，但已知将会在 $Q$ 个场景中的某一个发生。第 $j$ 个场景（$1 \leq j \leq Q$）的起点为 $S_j$，终点为 $G_j$，限制时间为 $T_j$ 秒。

参赛者理惠拾起 $1$ 个球需要 $1$ 秒，携带 $x$ 个球在道路上跑 $1$ 米需要 $x+1$ 秒。

给定 JOI 街道、球和场景的相关信息，请编写程序，判断对于每个场景，理惠是否存在完赛的方法。

输入通过标准输入给出，格式如下：

$N$ $L$ $X_1$ $X_2$ $\cdots$ $X_N$ $Q$ $S_1$ $G_1$ $T_1$ $S_2$ $G_2$ $T_2$ $\vdots$ $S_Q$ $G_Q$ $T_Q$

输出共 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）若在第 $j$ 个场景下理惠存在完赛的方法，则输出 Yes，否则输出 No。

小子任务

1.（$7$ 分）$N \leq 7$，$Q \leq 10$，$S_j = 0$，$G_j = 0$（$1 \leq j \leq Q$）。
2.（$7$ 分）$N \leq 7$，$Q \leq 10$。
3.（$10$ 分）$N \leq 14$，$Q \leq 10$。
4.（$28$ 分）$N \leq 100$，$Q \leq 10$。
5.（$10$ 分）$N \leq 2\,000$，$Q \leq 10$。
6.（$19$ 分）$N \leq 2\,000$。
7.（$19$ 分）无附加限制。

---

样例解释 1

在第 $1$ 个场景中，起点在地点 $0$，终点在地点 $100$，限制时间为 $403$ 秒。理惠可以如下方式在 $263$ 秒内完赛，因此第 $1$ 行输出 Yes。

顺序	行动	花费时间	累计时间
1	从地点 $0$ 移动到 $30$	$30$ 秒	$30$ 秒
2	拾起第 $1$ 个球	$1$ 秒	$31$ 秒
3	拾起第 $3$ 个球	$1$ 秒	$32$ 秒
4	从地点 $30$ 移动到 $80$	$150$ 秒	$182$ 秒
5	拾起第 $2$ 个球	$1$ 秒	$183$ 秒
6	从地点 $80$ 移动到 $100$，完赛	$80$ 秒	$263$ 秒

在第 $2$ 个场景中，起点和终点与第 $1$ 个场景相同，限制时间为 $300$ 秒。用同样方法，理惠可以在 $263$ 秒内完赛。因此第 $2$ 行输出 Yes。

在第 $3$ 个场景中，起点和终点与前两个场景相同，但限制时间为 $262$ 秒，无法在限制时间内完赛。因此第 $3$ 行输出 No。

此输入样例满足小子任务 $2, 3, 4, 5, 6, 7$ 的限制。

---

样例解释 2

在第 $1$ 个场景中，起点在地点 $0$，终点在地点 $0$，限制时间为 $403$ 秒。理惠可以如下方式在 $403$ 秒内完赛，因此第 $1$ 行输出 Yes。

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

第 $2, 3$ 个场景与第 $1$ 个场景起点、终点相同，但限制时间分别为 $300$ 秒和 $262$ 秒，均无法在限制时间内完赛。因此第 $2$ 行输出 No，第 $3$ 行输出 No。

此输入样例满足小子任务 $1, 2, 3, 4, 5, 6, 7$ 的限制。

---

样例解释 3

此输入样例满足小子任务 $2, 3, 4, 5, 6, 7$ 的限制。

数据范围与约定

• $1 \leq N \leq 500\,000$。
• $1 \leq L \leq 500\,000$。
• $0 \leq X_i \leq L$（$1 \leq i \leq N$）。
• $1 \leq Q \leq 500\,000$。
• $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 500\,000$（$1 \leq j \leq Q$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译