$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 합을 구하십시오.

입력

첫 번째 줄에는 세 정수 $N, M, Q$ ($1 \le N, M, Q \le 10^5$)가 주어집니다.

이어지는 $M$개의 줄에는 정점 $u$와 $v$를 잇는 가중치 $w$인 간선을 나타내는 세 정수 $u, v, w$ ($1 \le u, v \le N, 0 \le w < 2^{30}$)가 주어집니다. 이 문제에서는 다중 간선과 자기 루프가 허용됨에 유의하십시오.

이어지는 $Q$개의 줄에는 각 쿼리를 나타내는 두 정수 $l$과 $r$ ($1 \le l < r \le N$)이 주어집니다.

출력

각 쿼리에 대한 답을 한 줄에 하나씩 출력하십시오.

예제

입력 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