$N$ 個の頂点と $M$ 本の重み付き無向辺からなる連結グラフ $G$ があります。$G$ において、パスの重みは、そのパスに含まれるすべての辺の重みの XOR 和として定義されます。同じ辺を複数回通ることも許容され、その場合は通った回数分だけその辺の重みを XOR することに注意してください。

頂点 $u$ と $v$ に対して、$d(u, v)$ を $u$ から $v$ へのパスの重みの最大値とします。

以下の形式のクエリに $Q$ 回答える必要があります。 $l$ と $r$ が与えられたとき、$l \le i < j \le r$ を満たすすべての $i, j$ について、$d(i, j)$ の XOR 和を求めてください。

入力

1 行目に 3 つの整数 $N, M, Q$ ($1 \le N, M, Q \le 10^5$) が与えられます。

続く $M$ 行には、頂点 $u$ と $v$ を結ぶ重み $w$ の辺を表す 3 つの整数 $u, v, w$ ($1 \le u, v \le N, 0 \le w < 2^{30}$) が与えられます。この問題では多重辺や自己ループも許容されることに注意してください。

続く $Q$ 行には、各クエリを表す 2 つの整数 $l$ と $r$ ($1 \le l < r \le N$) が与えられます。

出力

各クエリについて、答えを 1 行ずつ出力してください。

入出力例

入力 1

8 10 7
1 2 662784558
3 2 195868257
3 4 294212653
4 5 299265014
6 5 72652580
6 7 29303370
7 8 183954825
2 1 752722885
5 3 197591314
8 4 877461873
4 8
5 7
6 7
2 3
7 8
3 4
2 7

出力 1

0
713437792
738051848
716356296
736682272
1003204975
987493236