問題文

ある国には $N$ 個の都市があり、それぞれ $1$ から $N$ までの番号がつけられています。これらの都市間を結ぶ $M$ 本の道路があり、$i$ 本目の道路は都市 $a_i$ と都市 $b_i$ を結ぶもので、$y_i$ 年に造られたものです。

この国の国民はとても心配性なので、あまりに古い道は事故の危険性が高いと考えて使わないことがあります。そこであなたは、この国の交通状況を調査することにしました。

$Q$ 人の国民の情報が与えられます。$j$ 人目の国民について、都市 $v_j$ に住んでおり、造られた年が $w_j$ 年以前 ($w_j$ 年ちょうども含む) であるような道路を使わないことがわかっています。

それぞれの国民に対し、その人が住んでいる都市から道路のみを使って行き来できるような都市の個数を求めてください。

制約

• $1 ≦ N ≦ 100,000$
• $0 ≦ M ≦ 200,000$
• $1 ≦ a_i,b_i ≦ N$
• $a_i ≠ b_i$
• $1 ≦ y_i ≦ 200,000$
• $1 ≦ Q ≦ 100,000$
• $1 ≦ v_j ≦ N$
• $0 ≦ w_j ≦ 200,000$

部分点

• $50$ 点分のテストケースでは、$N ≦ 1,000$, $M ≦ 2,000$, $Q ≦ 1,000$ をみたす。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $y_1$ : $a_M$ $b_M$ $y_M$ $Q$ $v_1$ $w_1$ : $v_Q$ $w_Q$

出力

$Q$ 行出力せよ。そのうちの $j$ 行目には、$j$ 人目の国民が道路のみを使って行き来可能な都市の個数を出力せよ。

入力例1

5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

出力例1

1
3
5

$Q$ 人それぞれの国民について、答えは以下のようになります。

• $1$ 人目は都市 $1$ に住んでおり、$2000$ 年以前に造られた道を使いません。都市 $1$ につながる唯一の道は $2000$ 年に造られているので、都市 $1$ 以外へ行くことができません。したがって答えは $1$ となります。
• $2$ 人目は都市 $1$ に住んでおり、都市 $2$ や $3$ へ行くことができます。しかし、$1999$ 年以前に造られた道を使わないので都市 $4$ へ行くことはできません。したがって答えは $3$ となります。
• $3$ 人目は $1995$ 年以前に造られた道を使いませんが、すべての道はそれより新しいため、すべての道をつかってすべての都市へ行くことができます。したがって答えは $5$ となります。

入力例2

4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

出力例2

3
3
4
1
1

入力例3

4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

出力例3

3
3
2
1

同じふたつの都市間を結ぶ道が $2$ 本以上あることや、すべての道を使っても辿り着けない都市がありうることに注意してください。