题目背景

后室（The Backrooms）是一个源于都市传说、现已发展为庞大跨媒介恐怖 IP 的异次元世界，核心设定是 “现实世界的故障漏洞”—— 当人类因意外触发某种 “空间 BUG”（如瞬间失神、穿越特定门扉、遭遇维度扭曲），就会脱离 “前室”（Frontrooms，即正常现实世界）。不幸的是，某天$Alice$在上课时突然走神了，醒来时就已经来到了后室世界的level 998244353层级。这是一个由多个独立房间以及多个连接任意两个房间的单向通道所构成的层级。

题目描述

Level 998244353层级由 $n$ 个房间（标号为从$1$到$n$）以及m个连接任意两个房间的单向通道组成。每条单向通道用$(u,v)$表示，其中 $u$ 为该通道的起点房间，$v$ 为该通道的终点房间，每个通道$(u,v)$的恐怖值为 $d_{（u,v）}$（注意所有通道都是单向的，即对于通道$(u,v)$，你只能从$u$房间经该通道到达 $v$ 房间）。换句话说，你可以把该层级看作一个加权有向图。

一开始，$Alice$拥有初始的san值(即耐力值)为 $x$，当她穿越一条恐怖值为 $d$ 的通道后，她的耐力值会变为$\lfloor \frac{x}{d} \rfloor$，（其中$\lfloor \rfloor$为向下取整函数），当$Alice$的耐力值下降到 $0$ 时，则被视为耐力值耗尽，便不能继续行动。

举个例子：假设$Alice$开始时的耐力值为 $9$ 。在穿越一条恐怖值为 $2$ 的通道后，她的耐力值变为 $4$ （因为 $⌊\frac{9}{2}⌋=4$）。如果她接着穿越另一个难度为 $2$ 的通道，她的耐力值会下降到 $2$ （ $⌊\frac{4}{2}⌋=2$ ）。最后，在穿越一条难度为 $3$ 的通道后，她的耐力值将变为 $0$ ( $⌊\frac{2}{3}⌋=0$ )，此时她的耐力值将耗尽。

由于$Alice$随时都不知道她在哪个房间，也不知道每条通道通向哪里，所以$Alice$提出了 $Q$ 个问题，对于第$i$个问题，她想问：如果她从房间 $p_i$ 开始，初始的耐力值为 $x_i$ ，每次她都会随机选择一条可以走的通道，那么在耐力值耗尽前，她至少要走多少条通道？（注意：如果$Alice$走过她以前走过的通道，她的耐力值仍会以同样的方式减少，即从 $x$ 变为 $\lfloor \frac{x}{d} \rfloor$）。

保证每个房间都至少有一条出去的通道（通道的起点房间和终点房间可能是相同的）。

输入格式

第一行包含三个整数 $n,m,Q (1 \leq n, Q \leq 2 \times 10^5,n \leq m \leq 5 \times 10^5)$，分别代表房间数量、单向通道数量和查询次数。

接下来的 $m$ 行分别包含三个整数$u, v, d( 1 \leq u, v\leq n,2 \leq d \leq 10^9)$，表示从$u$到 $v$ 的单向通道，难度值为$d$。

可以保证 $\forall i \in [1, n], \exists u, \mathrm{ s.t. } u = i$ .

接下来的$Q$行分别包含两个整数$p_i,x_i(1\leq p_i \leq n,1 \leq x_i \leq 10^9)$,表示第$i$个查询，即：如果Alice从房间 $p_i$ 出发，初始的耐力值为 $x_i$ ，那么在耐力值耗尽前，她必须经过的通道的个数的最小值是多少。

输出格式

输出 $Q$ 行，每行包含一个整数 $A_i$ ,表示对于第 $i$ 个查询，$Alice$在穿越至少 $A_i$ 个通道之后将耗尽耐力值。

样例

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

3
2
1
2
1
2
2

注意

本题输入数据量较大，请使用scanf与printf完成数据的读入与输出，或者在主函数开头添加下面代码以优化cin与cout:

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);

或者你可以手写快读。

再次注意，行末换行请使用\n,或者添加以下宏定义以使用endl：

#define endl '\n'

时间限制：$3s$

空间限制： $512 MiB$