XOR Cloister

Problem statement

An unusual rally game is popular at KU University. The circuit, which is the setting of this game, has N rest areas and M roads, and the i-th road is between the fi-th rest area and the ti-th rest area. There is one checkpoint on every road, and if you pass the checkpoint on road i, the score of pi will be added by XOR regardless of which direction you pass. It is added by XOR. I said it twice because it's important.

In this game, you can go through the same resting place or road as many times as you like, and even if you reach the goal, you can continue the rally as it is, but you can bypass the checkpoint in the middle of the road and go to another resting place. That is forbidden. Therefore, the reason why it is so popular is that you have to work hard to think about what kind of route you should take to get a high score.

There are Q participants this time, and it seems that the jth participant is supposed to start from the resting place of aj and go to the resting place of bj which is the goal. As a person on the management side, I decided to check the highest score of each participant in advance.

Input format

The input is given in the following format. The rest area number is 0-indexed.

N M Q f1 t1 p1 ... fM tM pM a1 b1 ... aQ bQ

Output format

Output the Q line, and output the maximum score obtained by the route from the ajth resting place to the bjth resting place on the jth line.

Constraint

• 1 ≤ N ≤ 105
• 0 ≤ M ≤ 2 × 105
• 1 ≤ Q ≤ 105
• 0 ≤ fi, ti <N, fi ≠ ti
• 0 ≤ pi <260
• 0 ≤ aj, bj <N
• From any resting place, you can reach any resting place by following the road.
• There is at most one road connecting the rest areas fi and ti.
• All input values ​​are integers.

A group of 60 test cases is set to judge this problem. In addition to the above constraints, the test cases included in this group also meet the following constraints.

• M ≤ 20

Examples

Input

5 5 3 0 1 7 1 2 22 2 3 128 3 4 128 4 2 128 0 1 0 0 3 4

Output

135 128 128

Input

None

Output

None

inputFormat

Input format

The input is given in the following format. The rest area number is 0-indexed.

N M Q f1 t1 p1 ... fM tM pM a1 b1 ... aQ bQ

outputFormat

Output format

Output the Q line, and output the maximum score obtained by the route from the ajth resting place to the bjth resting place on the jth line.

Constraint

• 1 ≤ N ≤ 105
• 0 ≤ M ≤ 2 × 105
• 1 ≤ Q ≤ 105
• 0 ≤ fi, ti <N, fi ≠ ti
• 0 ≤ pi <260
• 0 ≤ aj, bj <N
• From any resting place, you can reach any resting place by following the road.
• There is at most one road connecting the rest areas fi and ti.
• All input values ​​are integers.

A group of 60 test cases is set to judge this problem. In addition to the above constraints, the test cases included in this group also meet the following constraints.

• M ≤ 20

Examples

Input

5 5 3 0 1 7 1 2 22 2 3 128 3 4 128 4 2 128 0 1 0 0 3 4

Output

135 128 128

Input

None

Output

None

样例

5 5 3
0 1 7
1 2 22
2 3 128
3 4 128
4 2 128
0 1
0 0
3 4

135
128
128

</p>