AT_joig2022_f.タクシー 2 (Taxis 2)

题目要求

IOI 国家有 $N$ 个城市，编号从 $1$ 到 $N$；$M$ 条道路，编号从 $1$ 到 $M$ 。

想通过每条道路，都只能乘坐出租车。第 $i$（$1 \le i \le M$ ）条道路连接第 $A_i$ 个城市和第 $B_i$ 个城市，$C_i=1$ 表示出租车是红色的，$C_i=2$ 表示出租车是蓝色的。当然，出租车是收费的，收费如下：

• 设 $a$ 为上出租车前所持有的钱数，$b$ 为下车后你的钱数。
• 如果出租车是红色的，那么 $b=a - 1$ 。
• 如果出租车是蓝色的，那么 $b=\lfloor \frac{a+0.5}{2}\rfloor$。

你住在 IOI 国家的 $1$ 号城市。现在，你有 $Q$ 个朋友，第 $i$ 个朋友住在编号为 $t_i$ 的城市。现在你想知道，如果你想到达第 $i$ 个朋友家且到达后身上至少有 $1$ 元钱，那么你至少要带多少元钱？特别的，当这个钱数大于 $L$ 元时，输出 Large。

共 $M+Q+1$ 行。

第一行，四个正整数分别为 $N,M,Q,L$。

接下来的 $M$ 行，每行三个正整数 $A_i,B_i,C_i$。

接下来的 $Q$ 行，每行一个正整数 $t_i$。

共 $Q$ 行，每行一个正整数，表示每个询问的答案。

本题有捆绑测试。

对于 $100\%$ 的数据：

• $2 \le N \le 2\times10^5$，
• $N - 1 \le M \le 2\times10^5$，
• $1 \le Q \le 2\times10^5$，
• $1 \le L \le 10^9$，
• $\forall i \in[1,M],1 \le A_i \lt B_i \le N,C_i\in\{1,2\}$，
• $\forall i\neq j ,(A_i,B_i) \neq (A_j,B_j)$，
• $\forall i \in[2,Q],2 \le T_j \le N$，
• 在任意两个城市之间，你可以通过多条路径来回穿梭，
• 所有输入值均为整数。

部分分

子任务编号	$N\le$	$M\le$	$Q\le$	特殊性质	分数
1	$100$	$N-1$	$1$	$\textbf{A},\textbf{C}$	$9$
2	$2\times10^5$	$N-1$	$1$	$\textbf{A}$	$19$
3	$2\times10^5$	$N-1$	$2\times10^5$	$\textbf{A}$	$19$
4	$5\times10^4$	$5\times10^4$	$1$	$\textbf{B}$	$16$
5	$5\times10^4$	$5\times10^4$	$1$	无	$20$
6	$5\times10^4$	$5\times10^4$	$5\times10^4$	无	$12$
7	$2\times10^5$	$2\times10^5$	$2\times10^5$	无	$5$

特殊性质 $\textbf{A}$：$\forall i \in[1,M],(A_i,B_i)=(i,i+1)$。

特殊性质 $\textbf{B}$：$\forall i \in[1,M],C_i=1$。

特殊性质 $\textbf{C}$：$L\le100$。

由 OIer_Tan 翻译。