Problem statement

You have an undirected graph G with N vertices and M edges. Each side of G is numbered from 1 to M. The weights of the edges of G are terms in a Stern-Bocot sequence whose denominator is the number of the edge. A Stern-Bocot sequence is a sequence defined as follows:

• S1=0/1
• S2=1/1
• S2n=Sn/Sn+1
• S2n+1=Sn+1/Sn

For any two vertices u and v of G, find the minimum sum of the weights of the paths connecting u and v. The sum of the weights of a path is the sum of the weights of the sides in the path. If u and v are not connected, output -1.

---

Constraint

• 2≤N≤10^5
• 1≤M≤4×10^3
• 2≤Q<10^5
• 1≤ui,vi≤N
• ui≠vi
• G is a simple graph
• All inputs are integers

Input

The input is given from the standard input in the following format:

N M Q
u1 v1 w1
u2 v2 w2
⋮
uM vM wM
a1 b1
a2 b2
⋮
aQ bQ

Output

Output Q lines. In line i, output the minimum sum of the weights of the paths connecting ai and bi. If ai and bi are not connected, output -1. Note that all output is rational.

Test Case

Test Case 1:

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

Output 1:

2/1
2/1
2/1