Description

众所周知，炸弹鸭是鹅鸭杀中最为有游戏气氛的角色之一。

假设现在有一局鹅鸭杀游戏，游戏可以抽象的看成在一个 $n$ 个点 $m$ 条边的无向图上进行。每条边有边权 $w$ 代表两点之间的距离。每个人恰好占据一个节点。

但与原游戏不同，每个人在接到炸弹后只能丢给与自己直接有边相连的并且距离小于等于给定的限制 $k$ 的人，但炸弹鸭一次可能会塞给你很多个炸弹，且每次你只能把一个炸弹给一个满足条件且此次你还未传递炸弹的人，因此你需要把自己所有的炸弹按照上述条件传递出去，我们定义爆炸被避免当且仅当你手上的炸弹全被传递出去并且存在一个与你有边相连并且距离小于等于给定限制 $k$ 的人没有被你传递炸弹。

每次游戏炸弹鸭给人炸弹的概率是等可能的，因此你想知道，如果知道炸弹鸭每次给人的炸弹数以及给定限制 $k$ ，有多少位置的人不能够完成传递来避免爆炸。

Input

第一行三个整数 $n,m,q\ (1\le n\le 2 \times 10^5,1\le m,q\le 10^6)$，表示人数，边数和询问次数。

接下来 $m$ 行，每行三个整数 $u,v,w\ (1\le u,v\le n,u\neq v,1\le w\le 10^9)$ 分别表示在 $u$ 和 $v$ 之间有一条边，这条边长度为 $w$，保证数据无重边以及自环。

接下来 $q$ 行，每行两个整数 $d,k\ (1\le d\le n,1\le k\le 10^9)$，表示炸弹数和限制长度。

Output

输出共 $q$ 行。每行输出一个数字表示答案。

Samples

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

3
1

Note

对于第一组询问，如果炸弹鸭给 $1,3,4$ 号人炸弹均无法避免爆炸，如果给 $2$ 号人炸弹，他可以传给 $1$ 号人，此时有 $3$ 个人不能避免爆炸。

对于第二组询问，有且仅有 $4$ 号人无法避免爆炸。

Resources

The 21st UESTC Programming Contest Preliminary