問題文

ある国には 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 をみたす。

入力例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 本以上あることや、すべての道を使っても辿り着けない都市がありうることに注意してください。