题目背景

译自 第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\lt 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$
$\vdots$
$A_M$ $B_M$ $C_M$
$Q$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_Q$ $R_Q$ $X_Q$

输出格式

对于第 $i$ 个询问，如果可以达成，输出一行一个 $\texttt{Yes}$；否则输出一行一个 $\texttt{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

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

3 1 1000000000
1 2 6
1
1 1000000000 1000000000

No

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\sim 7$ 的限制。

样例 $3$ 解释

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

样例 $4$ 解释

该样例满足子任务 $5\sim 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\lt 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\le 10^9$（$1\le i\le Q$）。
• 输入的都是整数。

子任务

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