ADABRANC - Ada and Branches

Ada the Ladybug lives on a bush. A typical bush consists of some fruits connected with branches. Ada wants to travel between some fruits. Problem is that each edge can stand only some Xi weight (so if some creature with more weight would like to travel over the edge, it would break and the creature would fall of the bush).

Ada wants to make several travels so she asks you (for each such travel) to how many distinct fruits she can get?

Input

The first line of each test-case will contain three integers 2 ≤ N ≤ 105, the number of fruits, 1 ≤ M ≤ 2*105, the number of edges and 1 ≤ Q ≤ 3*105, the number of queries.

The next M lines will contain three integers 0 ≤ a, b < N (a ≠ b), the fruits which are connected by and edge and 1 ≤ Xi ≤ 105.

The next Q lines will contain two integers 0 ≤ a < N, the fruit Ada starts in and 1 ≤ Y ≤ 105, her actual weight.

NOTE Multiedges are allowed.

Output

For each query, output the number of fruits Ada can get to.

Example Input

4 4 3
1 2 4
2 3 3
3 0 4
0 1 3
1 3
1 4
1 5

Example Output

4
2
1

Example Input

8 10 8
1 3 3
1 2 2 
3 5 1
3 4 3
2 4 7
5 6 2
4 6 8
4 7 3
7 0 1
6 0 4
1 3
1 4
0 5
6 6
6 1
2 3
0 4
5 2

Example Output

7
1
1
3
8
7
4
8

Added by:Morass
Date:2017-10-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01

hide comments
2018-03-04 07:19:35
How is it possible for the bug to visit 3 fruits when it starts at 6 with weight 6
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.