클레프토크라트

회사에는 모든 직원에게 집과 사무실 사이의 최단 거리에 비례하는 금액을 환급해 주는 규정이 있다. 이 때문에 많은 직원이 최대한 멀리 이사해서 최대한 많은 환급금을 받으려 하는 허점이 생겼다.

한 직원이 이 규정을 너무 악용해서 회사를 파산시킬 위기에 놓였다. 내년에 규정을 폐지하기 전에 이 상황을 막아야 한다. 하지만 규칙은 엄격해서, 직원이 이동한 거리를 기록해 두는 한 환급해 줄 수밖에 없다.

그때 번뜩이는 아이디어가 떠올랐다. 어디에도 유클리드 거리를 써야 한다고 쓰여 있지 않다! 더 교묘한 거리 함수를 연구하기 시작했고, 이제 첫 시제품이 나왔다. 바로 XOR 거리다. 경로의 길이는 경로 위 간선 길이의 합이 아니라 XOR로 정의한다. 두 지점 사이의 거리는 두 지점을 잇는 최단 경로의 길이로 정의한다.

이 원리를 교통망에서 직원 각각의 위치에 차례로 적용해 시험해 보려 한다.

• 첫 줄에 세 정수 $n$ ($2 \leq n \leq 10^4$), $m$ ($n-1 \leq m \leq 10^5$), $q$ (${1 \leq q \leq 10^5}$)가 주어진다. 각각 노드의 수, 간선의 수, 질문의 수다.
• 다음 $m$개 줄에 간선이 하나씩 주어진다. 각 줄은 세 정수 $x$, $y$, $w$ ($1 \leq x,y \leq n$, $x\neq y$, $0 \leq w \leq 10^{18}$)로 이루어지며, 노드 $x$와 $y$ 사이에 길이 $w$인 무향 간선이 있음을 뜻한다.
• 다음 $q$개 줄에 질문이 하나씩 주어진다. 각 줄은 두 정수 $a$, $b$ ($1 \leq a,b \leq n$)로 이루어지며, 노드 $a$와 $b$ 사이의 최단 거리를 묻는다.

서로 다른 두 노드 사이에는 간선이 최대 하나만 있고, 모든 노드는 다른 모든 노드에서 도달할 수 있다.

각 질문마다 노드 $a$와 $b$ 사이의 최단 거리를 한 줄에 하나씩 출력한다.