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](\user\700210) 翻译。