题目描述

题目译自 JOI 2025 Final T3 「ミ・テレフェリコ / Mi Teleférico」

玻利维亚的首都拉巴斯不仅是一个旅游胜地，还因其缆车网络「我的缆车（Mi Teleférico）」而闻名。你现在正在拉巴斯旅游，想尽可能参观更多的景点。让我们简化现实中的情况，考虑以下设置。

拉巴斯有 $N$ 个缆车站，它们按海拔高度从低到高依次编号为 $1$ 到 $N$。此外，有 $M$ 条单向缆车路线，编号为 $1$ 到 $M$。还有 $P$ 家缆车公司，编号为 $1$ 到 $P$。每条路线由一家缆车公司管理。路线 $i$ $(1 \leq i \leq M)$ 从车站 $A_i$ 到车站 $B_i$ 运行，由公司 $C_i$ 管理。路线总是从低海拔车站运行到高海拔车站，即 $A_i < B_i$。

为了方便，拉巴斯交通局发行了通票。每张通票上有两个满足 $1 \leq l \leq r \leq P$ 的整数 $l$ 和 $r$，持有者可以乘坐由公司 $l$ 到 $r$ 管理的路线。即，对于满足 $1 \leq i \leq M$ 的整数 $i$，如果 $l \leq C_i \leq r$，则可以乘坐路线 $i$。同一张通票可以用于多条路线。我们将这种通票记为通票 $(l, r)$。

现在，编号为 $1$ 到 $Q$ 的 $Q$ 名游客来到拉巴斯。游客 $j$ $(1 \leq j \leq Q)$ 拥有通票 $(L_j, R_j)$ 和 $X_j$ 博利维亚诺现金。

游客的目标是仅使用现有的通票所能乘坐的路线，使得从车站 $1$ 出发可以到达所有其他车站。为此，游客 $j$ $(1 \leq j \leq Q)$ 可以进行以下操作，但每个游客最多只能交换一次：

1. 选择两个满足 $1 \leq l' \leq r' \leq P$ 的整数 $l'$ 和 $r'$。
2. 用通票 $(L_j, R_j)$ 交换通票 $(l', r')$。手续费为 $\left|L_j - l'\right| + \left|R_j - r'\right|$ 博利维亚诺。

你的任务是判断每个游客是否可以在其现金范围内实现目标。

输入格式

第一行包含三个用空格分隔的整数 $N,M,P$。

接下来 $M$ 行，每行包含三个用空格分隔的整数 $A_i, B_i, C_i$ $(1\leq i\leq M)$。

接下来一行包含一个整数 $Q$。

接下来 $Q$ 行，每行包含三个用空格分隔的整数 $L_j, R_j, X_j$ $(1\leq j\leq Q)$。

输出格式

输出 $Q$ 行。对于每个游客，如果可以在其现金范围内实现目标，输出 Yes，否则输出 No。

4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0

Yes
No
No
Yes

首先，对于游客 $1$，初始持有通票 $(3,7)$ 和 $0$ 玻利维亚诺现金。通过不进行通票交换，可以达成目标。因为通票 $(3,7)$ 能乘坐的线路有 $1,2,3,4$ 条。利用这 $4$ 条线路，可以从车站 $1$ 到达所有车站。

• 使用线路 $3$，可以从车站 $1$ 到车站 $2$。
• 使用线路 $1$ 和 $4$，可以从车站 $1$ 到 $2$ 再到 $3$。
• 使用线路 $3$ 和 $2$，可以从车站 $1$ 到 $2$ 再到 $4$。

因此，输出 Yes。

对于游客 $2$，初始持有通票 $(5,6)$ 和 $0$ 玻利维亚诺现金。不能达成目标。通票 $(5,6)$ 只能乘坐 $3$ 和 $4$ 号线路，不能从车站 $1$ 到 $4$。因为只有 $0$ 现金，不能进行通票交换。

因此，输出 No。

对于游客 $3$，也不能达成目标。对于游客 $4$，可以达成目标。

这个样例满足所有子任务的限制。

4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3

Yes
No
Yes

与样例 1 中线路相同。

首先，对于游客 $1$，初始持有通票 $(5,6)$ 和 $10$ 玻利维亚诺现金。通过以下通票交换可以达成目标：

1. 选择 $l' = 1, r' = 5$。
2. 用通票 $(5,6)$ 交换通票 $(1,5)$，手续费为 $|5-1|+|6-5|=5$ 玻利维亚诺。

因此，输出 Yes。

对于游客 $2$，初始持有通票 $(3,4)$ 和 $1$ 玻利维亚诺现金。无法通过任何通票交换达成目标。

因此，输出 No。

对于游客 $3$，可以达成目标。

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

3 1 1000000000
1 2 6
1
1 1000000000 1000000000

No

在这个路线上，无法从车站 $1$ 到达车站 $3$。因此，无论通票如何，游客都无法实现目标。

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

5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25

Yes
Yes
Yes
Yes
No

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

数据范围与提示

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

• $2 \leq N \leq 300000$。
• $1 \leq M \leq 300000$。
• $1 \leq P \leq 10^9$。
• $1 \leq A_i < B_i \leq N$ $(1 \leq i \leq M)$。
• $1 \leq C_i \leq P$ $(1 \leq i \leq M)$。
• $1 \leq Q \leq 400000$。
• $1 \leq L_j \leq R_j \leq P$ $(1 \leq j \leq Q)$。
• $0 \leq X_j \leq 10^9$ $(1 \leq j \leq Q)$。
• 输入的值均为整数。

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