AT_utpc2020_i UTPC Kingdom

在UTPC王国中，分布着 $N$ 座城镇与 $M$ 条街道。每条街道连接着两座城镇，其中第 $i$ 条街道连接的是城镇 $A_i$ 和城镇 $B_i$。考虑将城镇作为图中的顶点，街道作为边，由这些组成的图是一个无向连通图。图中可能存在多重边，但不含自环。 街道上会出现凶猛的怪物，第 $i$ 条街道的危险度由怪物的强度决定，是一个整数 $C_i$，并且这些危险度历来不同，即 $C_1, \ldots, C_M$ 互不相同。 一个旅行可以被定义为从一个城镇出发，沿着一些街道到达另一个城镇的经过街道序列。对旅行 $J = (J_1, J_2, \ldots, J_L)$，其危险度由以下公式计算：$\sum_{i=1}^{L} (10^6)^{C_{J_i}}$。两座城镇 $i$ 和 $j$ 的敌对程度定义为连接这两个城镇的所有可能旅行中危险度的最小值。如果无法通过任意旅行连接这两座城镇，那么敌对程度为极大值 $10^{10^{10}}$。 不幸的是，UTPC王国的一些街道因为灾害将在每一年遭到不可避免的中断。在第 $i$ 年，编号为 $T_i$ 的街道将因灾害无法通行。由于某条街道的关闭可能会增加两座城镇之间的敌对程度，我们可以通过永久封锁这些城镇之间的其他街道以维持国内稳定。此封锁可能会导致新的敌对城镇产生，因此该过程将根据需求反复进行，直到不再需要新的封锁。值得注意的是，一旦某条街道被关闭后，将不会再恢复通行。 我们需计算的是每年因首次封锁或灾害导致无法通行的街道编号之和 $S_i$。不过，编号 $T_i$ 是加密的，在输入中通过 $X_i$ 给出，满足 $S_{i-1} \oplus X_i = T_i$，从而可以解密出 $T_i$（$\oplus$ 表示异或运算，且 $S_0$ 为 $0$）。 同时，请注意：可能有些因灾害中断的街道已在之前被封锁。 ### 输入格式 输入将从标准输入中以如下形式给出： > $N$ $M$ > $A_1$ $B_1$ $C_1$ > $\vdots$ > $A_M$ $B_M$ $C_M$ > $Q$ > $X_1$ > $\vdots$ > $X_Q$ ### 输出格式 对于每个年度事件，输出 $Q$ 行。第 $i$ 行表示第 $i$ 年度首次因封锁或灾害导致无法通行的街道编号之和 $S_i$。 ### 数据范围与提示 - 所有输入均为整数。 - $1 \le N, M, Q \le 3 \times 10^5$ - $1 \le A_i, B_i \le N$ - $1 \le C_i \le 10^9$ - 危险度 $C_i$ 互不相同。 - $1 \le T_i = S_{i-1} \oplus X_i \le M$ - 街道编号 $T_i$ 互不相同。 - 构成的图是一个无向连通图，可能存在重边但没有自环。 #### 样例解释 1 第 1 年时，由于 $S_0 \oplus 1 = 1$，1 号街道受灾而无法通行，因此导致需要封锁 3 号和 4 号街道。于是，1 号、3 号和 4 号街道均属无法通行状态，因而 $S_1 = 8$。输出 8。第 2 年时，由于 $S_1 \oplus 10 = 2$，2 号街道因灾受损，新封锁的街道无需增加，故输出 2。 **本翻译由 AI 自动生成**

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ Q $ $ X_1 $ $ \vdots $ $ X_Q $

$ Q $ 行出力せよ。$ i $ 行目には、$ i $ 年目に初めて封鎖または災害によって通行不可能になった街道の番号の和 $ S_i $ を出力せよ。

### Sample Explanation 1 $ 1 $ 年目では $ S_0\ \oplus\ 1\ =\ 1 $ なので $ 1 $ 番目の街道が災害により通行不可能になります。 これにより、$ 3,\ 4 $ 番目の街道を封鎖しなければならなくなります。 $ 1,\ 3,\ 4 $ 番目の街道が通れなくなるので $ S_1=8 $ です。よって $ 8 $ を出力します。 $ 2 $ 年目では $ S_1\ \oplus\ 10\ =\ 2 $ より $ 2 $ 番目の街道が災害により通行不可能になります。 新しく封鎖するべき街道はありません。よって $ 2 $ を出力します。