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 suddenly 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 its 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