K - XOR回廊

問題文

KU大学では一風変わったラリーゲームが人気である． このゲームの舞台であるサーキットには，N 個の休憩所と M 個の道があり，i 番目の道は f_i 番目の休憩所と t_i 番目の休憩所の間にある． すべての道にはチェックポイントが一つずつ存在し，道 i のチェックポイントを通過するとどちらの向きで通っても p_i の得点がXORで加算される．XORで加算される．大事なことなので2回言いました．

このゲームでは，同じ休憩所や道を何度通っても良いし， ゴールにたどり着いてもそのままラリーを続行することができるが， 道の途中にあるチェックポイントを迂回して別の休憩所へ行くことは禁止されている． そのため，どのような道順をたどれば高い得点を取ることができるかを頑張って考えなければならない点が人気のある所以である．

今回は Q 人の参加者がいて，j 番目の参加者は a_j の休憩所からスタートして，ゴールである b_j の休憩所まで行くことになっているようだ． 運営側の人間としてそれぞれの参加者の最高得点を前もって調べておくことにした．

入力形式

入力は以下の形式で与えられる．なお休憩所の番号は0-indexedである．

N M Q
f1 t1 p1
...
fM tM pM
a1 b1
...
aQ bQ

出力形式

Q 行出力し，j 行目には a_j 番目の休憩所から b_j 番目の休憩所への経路で得られる得点の最大値を出力せよ．

制約

• 1 ≤ N ≤ 10⁵
• 0 ≤ M ≤ 2 × 10⁵
• 1 ≤ Q ≤ 10⁵
• 0 ≤ f_i, t_i < N, f_i ≠ t_i
• 0 ≤ p_i < 2⁶⁰
• 0 ≤ a_j, b_j < N
• どの休憩所からでも，道を辿っていけば任意の休憩所へたどり着ける．
• 休憩所 f_i,t_i 間を結ぶ道は高々一つしか存在しない．
• 入力値はすべて整数である．

この問題の判定には，60 点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• M ≤ 20

入出力例

入力例1

5 5 3
0 1 7
1 2 22
2 3 128
3 4 128
4 2 128
0 1
0 0
3 4

出力例1

135
128
128