Problem F
Liftkarta

The mountain Bergurbulgur consists of $N$ points and $M$ ski slopes where all slopes have a certain difficulty rating $S_i$. For every slope there exists a T-bar ski lift going up the slope. Since T-bar lifts can be very irritating, their difficulty is the same as the ski slope they’re going up on. On Bergurbulgur there is also $Q$ different families that have to go from some point $A_i$ to some other point $B_i$ through some sequence of lifts and slopes. Every family has $F_i$ members and every member has a certain skill rating, that indicates that they can go on all slopes and lifts that have a difficulty rating that is less or equal to the member’s skill rating. These skill ratings all follow a family specific formula of the form $k_i\cdot j + l_i$ where $j$ is the $j$th family member.

Given the information about all families, all points, ans ski slopes in Bergurbulgur, output for every family how many family members that can travel from $A_i$ to $B_i$.

Bergurbulgur is guaranteed to be a connected graph - which means that it is possible to get from every point to every other point on the mountain through some sequence of slopes and lifts. This means that a person with an infinite skill rating will always be able to reach every point.

Input

The first line contains three integers $N$, $M$ and $Q$ ($1\leq N, Q \leq 10^5$, $1\leq M \leq 5 \cdot 10^5$).
Then follows $M$ lines with three integers $u_i$, $v_i$, $S_i$ ($1\leq u_i, v_i \leq N$, $1\leq S_i \leq 10^9$), which indicates that there is a slope from point $u_i$ to point $v_i$ with difficulty rating $S_i$, for all $1 \leq i \leq M$.
On the following $Q$ lines there are five integers $A_i$, $B_i$, $F_i$ , $k_i$ and $l_i$ ($1 \leq A_i, B_i \leq N$, $1 \leq F_i \leq 10000$, $1 \leq k_i, l_i \leq 100000$) for all $1 \leq i \leq Q$. $l_i$ is the skill rating of the familymember with the lowest skill rating in the $i$th family, and $k_i$ is the coefficient which is described above.

Output

Output for every family a new line with an integer, the amount of family members in family $i$ that can travel from $A_i$ to $B_i$.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Explanation for sample 1

No matter how the first family chooses to get from point 6 to point 2 they have to go up the lift between 5 and 6, which has a difficulty rating of 7. This implies that only one family member can make it from point 6 to 2. For the second family they have to go through at least one slope or lift with a difficulty rating of 3, which means only 2 family members can make it from point 1 to point 4.

6 9 2
1 2 3
2 3 3
3 4 2
2 4 5
2 5 6
1 4 4
1 5 4
4 5 5
5 6 7
6 2 2 2 5 
1 4 3 1 2 

1
2