0660 - ドラゴン 2 (Dragon 2)

時間制限 4 秒 / メモリ制限 256 MB / 得点 100 / Writer root / x 1 / 統計 /


TLE
4sec
MLE
256MB
得点
100

JOI 平原では,人々はドラゴンたちと共に生きている.

JOI 平原は広大な座標平面であり,直交する X 軸と Y 軸が設定されている.X 座標が $x$, Y 座標が $y$ の点を ($x$, $y$) で表す.

JOI 平原には $N$ 匹のドラゴンが生息しており,$1$ から $N$ の番号が付けられている.また,ドラゴンに $M$ 種の種族があり,$1$ から $M$ の番号が付けられている.ドラゴン $i (1 \le i \le N)$ は常に JOI 平原の点 $(A_i, B_i)$ におり,その種族は $C_i$ である.JOI 平原には,すべての種族のドラゴンが生息しているとは限らない.

JOI 平原には人間の住む村が $2$ つあり,それぞれ JOI 平原の点 $(D_1, E_1)$ および点 $(D_2, E_2)$ に位置する.$2$ つの村は道で結ばれており,その道は村が存在する $2$ 点を結ぶ線分である.

点 $(A_1, B_1), \dots, (A_N, B_N)$ および点 $(D_1, E_1), (D_2, E_2)$ は,互いに異なり,これらの内のどの 3 点も同一直線上にない.

ドラゴンたちはしばしば種族間で対立する.種族 $a (1 \le a \le M)$ が種族 $b (1 \le b \le M, a \ne b)$ に対して敵意を抱くと,種族 $a$ に属するそれぞれのドラゴンが,種族 $b$ に属するすべてのドラゴンに向けて火の玉を吐く.火の玉は標的のドラゴンに向かって直進し,標的に到達したあとも同じ方向に飛び去っていく.すなわち,火の玉の辿る経路は半直線である.

種族間対立の際に,ドラゴンの吐いた火の玉が道を横切れば,道はダメージを受けるだろう.あなたは近い将来に起こりうるドラゴンたちの種族間対立として,考えられる $Q$ 個の可能性をリストアップした.

想定される種族間対立のそれぞれについて,道を横切る火の玉の個数を求めたい.

課題

ドラゴンたちおよび人間の村の情報と,ドラゴンたちの種族間対立の可能性のリストが与えられるとき,それぞれの種族間対立について,道を横切る火の玉の個数を求めるプログラムを作成せよ.

入力

標準入力から以下のデータを読み込め.

  • $1$ 行目には,$2$ 個の整数 $N, M$ が空白を区切りとして書かれている.これは,JOI 平原にはドラゴンが $N$ 匹おり,M 種の種族に分かれていることを表す.
  • 続く $N$ 行のうちの $i$ 行目 $(1 \le i \le N)$ には,$3$ 個の整数 $A_i, B_i, C_i$ が空白を区切りとして書かれている.これは,ドラゴン $i$ が JOI 平原の点 $(A_i, B_i)$ におり,種族が $C_i$ であることを表す.
  • 次の行には,$4$ 個の整数 $D_1, E_1, D_2, E_2$ が空白を区切りとして書かれている.これは,人間の住む村が JOI 平原の点 $(D_1, E_1)$ および点 $(D_2, E_2)$ に位置していることを表す.
  • 次の行には,整数 $Q$ が書かれている.これは,想定される種族間対立が $Q$ 個あることを表す.
  • 続く $Q$ 行のうちの $j$ 行目 $(1 \le j \le Q)$ には,$2$ 個の整数 $F_j, G_j$ が空白を区切りとして書かれている.これは,想定される種族間対立の $j$ 個目において,種族 $F_j$ が種族 $G_j$ に対して敵意を抱くことを表す.

出力

出力は $Q$ 行からなる.標準出力の $j$ 行目 $(1 \le j \le Q)$ には,$j$ 個目の種族間対立において道を横切る火の玉の個数を出力せよ.

制限

すべての入力データは以下の条件を満たす.

  • $2 \le N \le 30\ 000$.
  • $2 \le M \le N$.
  • $−1\ 000\ 000\ 000 \le A_i \le 1\ 000\ 000\ 000 (1 \le i \le N)$.
  • $−1\ 000\ 000\ 000 \le B_i \le 1\ 000\ 000\ 000 (1 \le i \le N)$.
  • $1 \le C_i \le M (1 \le i \le N)$.
  • $−1\ 000\ 000\ 000 \le D_1 \le 1\ 000\ 000\ 000$.
  • $−1\ 000\ 000\ 000 \le E_1 \le 1\ 000\ 000\ 000$.
  • $−1\ 000\ 000\ 000 \le D_2 \le 1\ 000\ 000\ 000$.
  • $−1\ 000\ 000\ 000 \le E_2 \le 1\ 000\ 000\ 000$.
  • $N + 2$ 個の点 $(A_1, B_1), \dots, (A_N, B_N), (D_1, E_1), (D_2, E_2)$ は互いに異なり,どの $3$ 点も同一直線上にない.
  • $1 \le Q \le 100\ 000$.
  • $1 \le F_j \le M (1 \le j \le Q)$.
  • $1 \le G_j \le M (1 \le j \le Q)$.
  • $F_j \ne G_j (1 \le j \le Q)$.
  • $(F_j, G_j) \ne (F_k, G_k) (1 \le j \lt k \le Q)$.

小課題

この課題では小課題は全部で $3$ 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題 1 [15 点]

  • $N \le 3 000$.

小課題 2 [45 点]

  • $Q \le 100$.

小課題 3 [40 点]

追加の制限はない.

入出力例

入力例 1

4 2
0 1 1
0 -1 1
1 2 2
-6 1 2
-2 0 2 0
2
1 2
2 1

出力例 1

1
2

$1$ 個目の種族間対立では,

  • ドラゴン $1$ がドラゴン $3$ に向けて吐いた火の玉は道を横切らない.
  • ドラゴン $1$ がドラゴン $4$ に向けて吐いた火の玉は道を横切らない.
  • ドラゴン $2$ がドラゴン $3$ に向けて吐いた火の玉は道を横切る.
  • ドラゴン $2$ がドラゴン $4$ に向けて吐いた火の玉は道を横切らない.

よって道を横切る火の玉は $1$ 個である.

$2$ 個目の種族間対立では,

  • ドラゴン $3$ がドラゴン $2$ に向けて吐いた火の玉は道を横切る.
  • ドラゴン $4$ がドラゴン $1$ に向けて吐いた火の玉は道を横切らない.
  • ドラゴン $4$ がドラゴン $2$ に向けて吐いた火の玉は道を横切らない.

よって道を横切る火の玉は $2$ 個である.

入力例 2

3 2
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 2

出力例 2

1

入力例 3

6 3
2 -1 1
1 0 1
0 3 2
2 4 2
5 4 3
3 9 3
0 0 3 3
6
1 2
1 3
2 1
2 3
3 1
3 2

出力例 3

4
2
4
0
2
1