Mohan decides to go on a walk through \(N\) places in the city. She wants to maximize the beauty of the scenery of her walks. The places she can visit are connnected by \(M\) bidirectional roads, with the \(i\)th road having a beauty score of \(w_{i}\) connecting \(u_{i}\) to \(v_{i}\), and with no limit as to how many times she can travel across each road. The beauty of her walks are evaluated by the bitwise OR of all the beauty scores of the roads she travels on.

Mohan already has decided where she wants to start and end over \(Q\) days, wanting to start her walk on the \(i\)th day at \(a_{i}\) and ending at \(b_{i}\). For each day, tell her the maximum beauty possible from \(a_{i}\) to \(b_{i}\).

Constraints

\(1 \le u_{i}, v_{i}, a_{i}, b_{i} \le N\)

\(1 \le w_{i} \le 10^{9}\)

Subtask 1 [30%]

\(1 \le N, M \le 50\)

\(1 \le Q \le 500\)

Subtask 2 [70%]

\(1 \le N, M \le 10^{5}\)

\(1 \le Q \le 10^{6}\)

Input Specification

The first line will contain two space seperated integers \(N\) and \(M\).

The next \(M\) lines will contain \(u_{i}\), \(v_{i}\) and \(w_{i}\), describing the \(i\)th road.

The next line will contain the integer \(Q\).

The next \(Q\) lines will contain 2 space seperated integer \(a_i\) and \(b-I\) meaning that on day \(i\) Mohan wants to walk from \(a\) to \(b\).

Output Specification

Output \(Q\) lines, the maxmimum beauty score possible for each day. If it is impossible to traverse, output -1.

Sample Input

6 6
1 4 1
1 2 4
1 3 2
2 3 1
2 4 3
5 6 9
3
1 4
6 2
5 6

Sample Output

7
-1
9

Explanation for Sample Output:

Mohan can go from 1 -> 2 -> 4. Having a score of (4 OR 3) = 7

Mohan cannot go from 6 to 2.

Mohan can go from 5 -> 6. Having a score of 9