There is an undirected graph with points and edges.

where the point set is and the edge set is . And edge weighted value.

Note that a not-simple path of is ，where represents the number of the  th passing point in the path.

When a not-simple path meets the following two conditions, it is legal: 

• for，there is。

• for ，there is 。

Now there are inquiries. Each inquiry will give three values , which you need to find out:  

In this problem：

• Is the number of edges that the path passes through.

• Represents the weight of an edge from  to .

• Represents bitwise xor.

Simply put, you need to find " the sum of bitwise xor sums of all non-simple paths from to , and the number of edges is exactly ". 

The answer is modulo

输入描述:

Two integers  in the first line represent the number of points and edges of the graph.

Next  lines, each line contains two integers , representing an edge.

The next line is an integer , indicating the number of inquiries.

Next  lines, each line with three integers , represent an inquiry.



Ensure that there is no self-ring and no double edge.

输出描述:

There are  lines in total, each line contains an integer, and the integer in the  line represents the answer of the  th inquiry.

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

4
5
25