Problem Statement

The country of kazuppa has $N$ towns numbered from $1$ to $N$ and $M$ roads numbered from $1$ to $M$. Road $i$ bidirectionally connects town $U_i$ and town $V_i$, and its length is $L_i$.

In the country of kazuppa, a virus called "Itsukin" spreads once every few years. To prepare for this situation, the country of kazuppa has decided to consider the following problem.

Itsukin with infectivity $p$ breaks out in town $t$.

When Itsukin is present in some town $u$, it also breaks out in any town $v$ directly adjacent to that town by a road of length at most $p$.

Answer the number of towns where Itsukin breaks out.

There are $Q$ situations to consider for this problem. For the $i$-th situation, answer this problem with $p=P_i$ and $t=T_i$.

Constraints

• $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$
• All input values are integers.

Subtasks

This problem has partial scoring by subtasks.

Input

$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$

Output

Print $Q$ lines.

On the $i$-th line, print the answer for the $i$-th situation.

Sample

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