P11664 [JOI 2025 Final] 缆车 / Mi Teleférico

译自 [第24回日本情報オリンピック 本選](https://contests.ioi-jp.org/joi-ho-2025/index.html) 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}$。

### 样例解释 #### 样例 $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）无额外限制。