#P1659E. AND-MEX Walk
AND-MEX Walk
Description
There is an undirected, connected graph with vertices and weighted edges. A walk from vertex to vertex is defined as a sequence of vertices (which are not necessarily distinct) starting with and ending with , such that and are connected by an edge for .
We define the length of a walk as follows: take the ordered sequence of edges and write down the weights on each of them in an array. Now, write down the bitwise AND of every nonempty prefix of this array. The length of the walk is the MEX of all these values.
More formally, let us have where is the weight of the edge between and . Then the length of the walk is given by , where denotes the bitwise AND operation.
Now you must process queries of the form u v. For each query, find the minimum possible length of a walk from to .
The MEX (minimum excluded) of a set is the smallest non-negative integer that does not belong to the set. For instance:
- The MEX of is , because does not belong to the set.
- The MEX of is , because and belong to the set, but does not.
- The MEX of is because , , and belong to the set, but does not.
The first line contains two integers and (; ).
Each of the next lines contains three integers , , and (, ; ) indicating an undirected edge between vertex and vertex with weight . The input will not contain self-loops or duplicate edges, and the provided graph will be connected.
The next line contains a single integer ().
Each of the next lines contains two integers and (, ), the description of each query.
For each query, print one line containing a single integer — the answer to the query.
Input
The first line contains two integers and (; ).
Each of the next lines contains three integers , , and (, ; ) indicating an undirected edge between vertex and vertex with weight . The input will not contain self-loops or duplicate edges, and the provided graph will be connected.
The next line contains a single integer ().
Each of the next lines contains two integers and (, ), the description of each query.
Output
For each query, print one line containing a single integer — the answer to the query.
Samples
Note
The following is an explanation of the first example.
Here is one possible walk for the first query:
The array of weights is . Now if we take the bitwise AND of every prefix of this array, we get the set . The MEX of this set is . We cannot get a walk with a smaller length (as defined in the statement).