The network of your office is composed of several computers and bidirectional links. Each link connects a given pair of computers and has an access value. Each user in the network has an access privilege, and is able to use any link with access value not exceeding his access privilege.

Everything was fine until you notice that a bunch of hackers are accessing the network. You know that if there is a link between computers A and B, with access value V, and a hacker with access privilege of at least V controls A, then he can control B. Hackers wish to control the most important computers by exploiting problems in the network. They are trying to increase their access privileges in order to use the links, and your task is to measure how safe the network is.

Given the description of the network, the computer each hacker currently controls and the target computer each hacker wishes to control, you need to calculate the minimum access privilege each hacker needs to get in order to control his target computer. Hackers act independently, neither they collaborate nor interfere with each other. This means that each hacker may control each computer and use each link independently of what the other hackers do.

Input

Each test case is described using several lines. The first line contains three integers C, L and H, indicating the number of computers, links and hackers in the network, respectively (2 ≤ C ≤ 3000, 1 ≤ L, H ≤ 10⁵).

Each computer is identified by an integer number between 1 and C. Each of the next L lines describes a different bidirectional link using three integers A, B and V; the numbers A and B identify two distinct computers that are the endpoints of the link (1 ≤ A < B ≤ C); the number V is the access value of the link, that is, any hacker must have an access privilege of at least V to use the link (1 ≤ V ≤ 10⁹).

Each of the last H lines describes a different hacker using two distinct integers S and T that identify the computer that the hacker currently controls and the computer that the hacker wishes to control, respectively (1 ≤ S, T ≤ C).

You may assume that within each test case no two links connect the same pair of computers, and that for any pair of computers there is at least one sequence of links that allow to reach one computer starting from the other.

The end of input is indicated with a line containing the number −1 three times.

Output

For each test case, output a single line with H integers representing the minimum access privilege each hacker needs to achieve his goal. The result for each hacker must appear in the same order that the hackers are described in the input.

Example

Input:
5 6 4
1 2 4
1 3 5
2 4 3
2 5 1
3 4 2
4 5 2
3 2
2 4
1 5
3 1
2 1 1
1 2 1
2 1
2 1 3
1 2 1000000000
2 1
2 1
1 2
-1 -1 -1

Output:
2 2 4 4
1
1000000000 1000000000 1000000000