第 4 题我的缆车 (`mitelefrico`)

时间限制 1.0 s · 空间限制 256 MB · 133 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 mitelefrico.in，输出文件 mitelefrico.out。

译自第24回日本情報オリンピック本選 T3。

Mi Teleférico 指的是连接玻利维亚拉巴斯市（La Paz）及埃尔阿尔托市（El Alto）的缆车系统。

题目描述

给定一张 $N$ 个点 $M$ 条边的有向无环图。这张有向图的边是由 $P$ 个公司（编号 $1 \sim P$ ）修建的，每条边恰好被一个公司修建。

节点标号 $1 \sim N$ ，第 $i$ （ $1 \le i \le M$ ）条边由节点 $A_i$ 指向节点 $B_i$ ，且是公司 $C_i$ 修建的。这里，保证 $A_i < B_i$ 。

有 $Q$ 个询问，每个询问给定区间 $[L, R]$ （ $1 \le L \le R \le P$ ）和钱数 $X$ 。目标是从 1 号点只经过编号 $\in [L, R]$ 的公司修建的边，可以到达其他任意一个节点。

为此，可以选择一个新的区间 $[l', r']$ （ $1 \le l' \le r' \le P$ ），将 $[L, R]$ 变为 $[l', r']$ 。这会花费 $|L - l'| + |R - r'|$ 的代价，这个操作至多只能执行一次。操作的代价必须不大于钱数 $X$ 。

对于每个询问，判断是否能够达成目标。

输入格式

如下所示：

N M P
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_M B_M C_M
Q
L_1 R_1 X_1
L_2 R_2 X_2
⋮
L_Q R_Q X_Q

输出格式

对于第 $i$ 个询问，如果可以达成，输出一行一个 Yes；否则输出一行一个 No。

样例

样例 1

输入：

输出：

Yes
No
No
Yes

样例 2

输入：

输出：

Yes
No
Yes

样例 3

输入：

3 1 1000000000
1 2 6
1
1 1000000000 1000000000

输出：

No

样例 4

输入：

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

提示

样例解释

样例 1 解释

第 1 个询问中， $[3, 7]$ 已经可以满足条件，无需进行操作。

第 2 个询问中， $[5, 6]$ 不满足条件，然后无法进行任何操作，所以无法达成目标。

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

样例 2 解释

第 1 个询问中，选择 $l' = 1, r' = 5$ ，花费 5 的代价可以达成目标。

该样例满足子任务 2, 3, 5 ~ 7 的限制。

样例 3 解释

该样例满足子任务 6, 7 的限制。

样例 4 解释

该样例满足子任务 5 ~ 7 的限制。

数据范围

$2 \le N \le 3 \times 10^5$ .
$1 \le M \le 3 \times 10^5$ .
$1 \le P \le 10^9$ .
$1 \le A_i < B_i \le N$ （ $1 \le i \le M$ ）.
$1 \le C_i \le P$ （ $1 \le i \le M$ ）.
$1 \le Q \le 4 \times 10^5$ .
$1 \le L_i \le R_i \le P$ （ $1 \le i \le Q$ ）.
$0 \le X_i < 10^9$ （ $1 \le i \le Q$ ）.
输入的都是整数。

子任务

(7pts) $N, M, Q \le 50$ ， $X_i = 0$ （ $1 \le i \le Q$ ）.
(8pts) $P \le 10$ .
(11pts) $P \le 100$ .
(23pts) $P \le 3 \times 10^5$ ， $X_i = 0$ （ $1 \le i \le Q$ ）.
(9pts) $P \le 3 \times 10^5$ .
(22pts) $N, M \le 8\,000$ .
(20pts) 无额外限制.

第 4 题 我的缆车 (mitelefrico)