AT_utpc2020_i UTPC Kingdom

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_i UTPC 王国には $ N $ 個の街 $ 1,\ \ldots,\ 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 $ の仲の悪さを、$ 2 $ つの街を繋ぐ旅の危険度の最小値で定めます。そのような旅が存在しないとき、仲の悪さは $ 10^{10^{10}} $ とします。 UTPC 王国はとても不運な王国で、$ i $ 年目には、$ T_i $ 番目の街道が災害で通行不可能になります。 街道が通行不可能になったことで仲の悪さが増加した街の組はいがみあってしまい、とても危険な状態になってしまいます。 このような街の組を直接結ぶ街道があれば、それらを同時に封鎖することで通行不可能にし、国の平穏を保つことにしました。また、この措置の影響でいがみあっている街の組が出来てしまった場合、同様の措置を繰り返します。 この操作は有限回で終わることが示されます。一度通行不可能になった街道が再度通行可能になることはありません。 $ Q $ 年間の災害で通行不可能になった街道の情報が与えられます。 $ i $ 年目に初めて封鎖または災害によって通行不可能になった街道の番号の和 $ S_i $ を出力してください。 ただし、$ T_i $ は暗号化されていて直接読み込むことはできません。 $ X_i $ が入力として与えられ、$ S_{i-1}\ \oplus\ X_i\ =\ T_i $ として、$ T_i $ が復元されます。($ \oplus $ は xor を表し、$ S_0 $ は $ 0 $ であるとします。) また、災害によって通行不可能になる街道が既に封鎖されている場合もあることに注意してください。 ### 制約 - 入力はすべて整数である。 - $ 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 $ は相異なる。 - 街を頂点、街道を辺としたグラフは無向連結グラフで、多重辺は含まれる可能性があるが自己ループは含まれない。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ を出力します。