You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 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)$。
• 输入的值均为整数。

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