問題文

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 は相異なる。
• 街を頂点、街道を辺としたグラフは無向連結グラフで、多重辺は含まれる可能性があるが自己ループは含まれない。

入力例1

3 4
1 2 1
2 3 2
3 1 3
1 2 4
2
1
10

出力例1

8
2

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

2 年目では S_1 \oplus 10 = 2 より 2 番目の街道が災害により通行不可能になります。 新しく封鎖するべき街道はありません。よって 2 を出力します。