問題文

kazuppa国には $1$ から $N$ までの番号が付けられた $N$ 個の町と $1$ から $M$ までの番号が付けられた $M$ 個の道があります。道 $i$ は町 $U_i$ と町 $V_i$ を双方向に結び、長さは $L_i$ です。

kazuppa国では「いつ菌」と呼ばれるウイルスが数年に一度蔓延します。kazuppa国ではこの事態に備えるために以下の問題を考えることにしました。

感染力 $p$ のいつ菌が町 $t$ で発生する。

ある町 $u$ でいつ菌が発生しているとき、長さが $p$ 以下の道で直接隣り合っている町 $v$ でもいつ菌が発生する。

いつ菌が発生する町はいくつあるか答えよ。

この問題には $Q$ 個のシチュエーションが考えられます。$i$ 個目のシチュエーションでは $p=P_i$、$t=T_i$ であるとしてこの問題に答えてください。

制約

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 4\times 10^5$
• $1\leq U_i< V_i\leq N$
• $1\leq L_i\leq 10^9$
• $1\leq Q\leq 2\times 10^5$
• $1\leq P_i\leq 10^9$
• $1\leq T_i\leq N$
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$N\ M$
$U_1\ V_1\ L_1$
$U_2\ V_2\ L_2$
$\vdots$
$U_M\ V_M\ L_M$
$Q$
$P_1\ T_1$
$P_2\ T_2$
$\vdots$
$P_Q\ T_Q$

出力

$Q$ 行出力してください。

$i$ 行目には、 $i$ 個目のシチュエーションに対する答えを出力してください。

サンプル

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

3
1
5
3