XOR

A new city called Xor was recently built in Croatia. The city has $N$ intersections and $M$ two-way roads. Each road connects a pair of intersections and has a length, a non-negative integer. Mirko moved to Xor and plans to take taxis often. Taxi fares in Xor are computed in an unusual way. The price of a ride is the bitwise XOR of the lengths of the roads the taxi drives along. For example, a ride along roads of lengths 3, 4 and 6 costs 3 XOR 4 XOR 6 = 1. During one ride the taxi may drive along the same road several times, and every pass counts toward the price.

Mirko wants to spend as little as possible on his rides. Each ride is given by a starting intersection $A$ and a destination intersection $B$, and you have to find the smallest possible price of that ride. The taxi may drive through intersection $B$ and keep going, but the ride has to end at $B$.

The first line contains the number of intersections $N$ and the number of roads $M$. ($1 \le N, M \le 200\,000$)

Each of the next $M$ lines describes one road with three integers $A$, $B$ and $C$ ($1 \le A < B \le N$, $0 \le C \le 1\,000\,000\,000$), meaning that a road of length $C$ connects intersections $A$ and $B$.

No two roads connect the same pair of intersections.

Every intersection can be reached from every other intersection.

The next line contains the number of Mirko's rides $Q$. ($1 \le Q \le 200\,000$)

Each of the next $Q$ lines describes one ride with the starting intersection $A$ and the destination intersection $B$. ($1 \le A, B \le N$)

For each of the $Q$ rides print the smallest possible price on its own line, in the order the rides are given in the input.

Note that bit $i$ of $A$ XOR $B$ is 1 exactly when bit $i$ of $A$ and bit $i$ of $B$ differ. (for example, 0011 XOR 0101 = 0110)

In the first example the taxi visits intersections 1, 2, 3, 4, 5, 3, 2 in that order, and the price is 3 XOR 9 XOR 2 XOR 6 XOR 7 XOR 9 = 0.