KU大学では一風変わったラリーゲームが人気である. このゲームの舞台であるサーキットには,N 個の休憩所と M 個の道があり,i 番目の道は fi 番目の休憩所と ti 番目の休憩所の間にある. すべての道にはチェックポイントが一つずつ存在し,道 i のチェックポイントを通過するとどちらの向きで通っても pi の得点がXORで加算される.XORで加算される.大事なことなので2回言いました.
このゲームでは,同じ休憩所や道を何度通っても良いし, ゴールにたどり着いてもそのままラリーを続行することができるが, 道の途中にあるチェックポイントを迂回して別の休憩所へ行くことは禁止されている. そのため,どのような道順をたどれば高い得点を取ることができるかを頑張って考えなければならない点が人気のある所以である.
今回は Q 人の参加者がいて,j 番目の参加者は aj の休憩所からスタートして,ゴールである bj の休憩所まで行くことになっているようだ. 運営側の人間としてそれぞれの参加者の最高得点を前もって調べておくことにした.
入力は以下の形式で与えられる.なお休憩所の番号は0-indexedである.
N M Q f1 t1 p1 ... fM tM pM a1 b1 ... aQ bQ
Q 行出力し,j 行目には aj 番目の休憩所から bj 番目の休憩所への経路で得られる得点の最大値を出力せよ.
この問題の判定には,60 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.
5 5 3 0 1 7 1 2 22 2 3 128 3 4 128 4 2 128 0 1 0 0 3 4
135 128 128