G. Exploration
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice is exploring a dangerous large maze. This maze has $$$n$$$ caves (labeled from $$$1$$$ to $$$n$$$) and $$$m$$$ one-way passages connecting any two of these caves (because some traps in the passages make it difficult to return once passed). Each passage is represented as $$$(u, v)$$$, where $$$u$$$ is the starting cave and $$$v$$$ is the destination cave. Each passage $$$(u, v)$$$ has a difficulty value $$$d_{(u, v)}$$$. In other words, you can think of the entire cave system as a weighted directed graph.

At the beginning, Alice has an initial stamina (or it can be called 'energy') $$$x$$$. When she traverses a passage with difficulty value $$$d$$$, her stamina $$$x$$$ changes to $$$\lfloor \frac{x}{d} \rfloor$$$ (where $$$\lfloor\ \rfloor$$$ is the floor function). When Alice's stamina drops to $$$0$$$, it is considered that her stamina is exhausted, and she can no longer continue exploring.

For a example: Suppose Alice starts with a stamina value of $$$9$$$. After traversing a passage with difficulty $$$2$$$, her stamina becomes $$$4$$$ (since $$$\lfloor \frac{9}{2}\rfloor = 4$$$). If she then traverses another passage with difficulty $$$2$$$, her stamina drops to $$$2$$$ ($$$\lfloor \frac{4}{2}\rfloor = 2$$$). Finally, after traversing a passage with difficulty $$$3$$$, her stamina becomes $$$0$$$ ($$$\lfloor \frac{2}{3}\rfloor = 0$$$), at which point her stamina is exhausted.

Since Alice has a poor sense of direction in the maze, at any point during her exploration, she does not know which cave she is currently in or where each passage leads. Therefore, Alice has $$$Q$$$ questions. For the $$$i$$$-th question, she wants to ask: If she starts from cave $$$p_i$$$ with an initial stamina of $$$x_i$$$, and each time she randomly chooses a passage she can take, what is the minimum number of passages she must traverse before her stamina is exhausted? ($$$\textbf{Note}$$$: If Alice traverses a passage she has taken before, her stamina will still decrease in the same way, i.e., from $$$x$$$ to $$$\lfloor \frac{x}{d}\rfloor$$$.)

It is guaranteed that every cave has at least one outgoing one-way passage (the starting and ending caves of a passage may be the same).

Input

The first line contains three integers $$$n,m,Q$$$ ($$$1 \leq n, Q \leq 2 \times 10^5,n \leq m \leq 5 \times 10^5$$$), representing the number of caves, the number of passages, and the number of queries respectively.

The following $$$m$$$ lines each contain three integers $$$u, v, d$$$ ($$$1 \leq u, v\leq n,2 \leq d \leq 10^9$$$), indicating a one-way passage from $$$u$$$ to $$$v$$$ with difficulty value $$$d$$$.

It is guaranteed that $$$\forall i \in [1, n], \exists u, \mathrm{ s.t. } \ u = i$$$.

The next $$$Q$$$ lines each contain two integers $$$p_i,x_i$$$ ($$$1 \leq p_i \leq n,1 \leq x_i \leq 10^9$$$),representing the $$$i$$$-th query: if Alice starts from cave $$$p_i$$$ with initial stamina $$$x_i$$$, what is the minimum number of passages she must traverse before her stamina is exhausted.

Output

Output $$$Q$$$ lines, each containing a single integer $$$A_i$$$, indicating that for the $$$i$$$-th query, Alice will exhaust her stamina after traversing a minimum of $$$A_i$$$ passages.

Example
Input
3 4 7
1 2 2
2 3 4
3 2 3
3 3 2
1 10
2 9
3 2
2 8
3 1
1 7
2 4
Output
3
2
1
2
1
2
2