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