XOR

크로아티아에 Xor라는 새 도시가 생겼다. 이 도시에는 교차로 $N$개와 양방향 도로 $M$개가 있다. 각 도로는 교차로 두 곳을 잇고, 길이는 음이 아닌 정수다. Xor로 이사한 미르코는 택시를 자주 탈 생각이다. Xor의 택시 요금은 특이하게 계산한다. 택시가 지나간 도로 길이를 모두 비트 XOR한 값이 요금이다. 예를 들어 길이가 3, 4, 6인 도로를 지나면 요금은 3 XOR 4 XOR 6 = 1이다. 한 번의 운행에서 택시가 같은 도로를 여러 번 지나도 되고, 지날 때마다 요금에 들어간다.

미르코는 택시 요금을 최대한 적게 쓰려고 한다. 각 운행은 출발 교차로 $A$와 도착 교차로 $B$로 주어지고, 그 운행의 가능한 가장 작은 요금을 구해야 한다. 택시는 교차로 $B$를 지나쳐 계속 달려도 되지만, 운행은 반드시 $B$에서 끝나야 한다.

첫째 줄에 교차로 수 $N$과 도로 수 $M$이 주어진다. ($1 \le N, M \le 200\,000$)

다음 $M$개 줄에 도로가 하나씩 주어진다. 각 줄에는 정수 $A$, $B$, $C$가 주어지고 ($1 \le A < B \le N$, $0 \le C \le 1\,000\,000\,000$), 교차로 $A$와 $B$를 잇는 길이 $C$인 도로를 뜻한다.

같은 교차로 쌍을 잇는 도로가 둘 이상 주어지는 경우는 없다.

어느 교차로에서든 다른 모든 교차로로 갈 수 있다.

다음 줄에 미르코의 운행 횟수 $Q$가 주어진다. ($1 \le Q \le 200\,000$)

다음 $Q$개 줄에 운행이 하나씩 주어진다. 각 줄에는 출발 교차로 $A$와 도착 교차로 $B$가 주어진다. ($1 \le A, B \le N$)

$Q$개 운행 각각에 대해 가능한 가장 작은 요금을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

참고로 $A$ XOR $B$의 2진법 $i$번째 자리는 $A$와 $B$의 $i$번째 자리가 서로 다를 때만 1이다. (예: 0011 XOR 0101 = 0110)

첫 번째 예제에서 미르코의 택시가 지나는 교차로는 순서대로 1, 2, 3, 4, 5, 3, 2이고, 요금은 3 XOR 9 XOR 2 XOR 6 XOR 7 XOR 9 = 0이다.