드래곤 2

JOI 평면에는 드래곤과 사람이 함께 살고 있다. JOI 평면은 X좌표와 Y좌표로 이루어진 넓은 좌표 평면이다. X좌표가 $x$, Y좌표가 $y$인 점은 $(x, y)$로 나타낸다.

드래곤은 $N$마리이며 1번부터 $N$번까지 번호가 붙어 있다. 부족은 $M$개이며 1번부터 $M$번까지 번호가 붙어 있다. $i$번 드래곤은 $(A_i, B_i)$에 있고 $C_i$번 부족에 속한다. 평면에 드래곤이 살지 않는 부족도 있다.

사람의 마을은 $(D_1, E_1)$과 $(D_2, E_2)$에 있다. 도로는 두 마을을 잇는 선분이다.

부족끼리 적대 관계가 생길 수 있다. 부족 $a$($1 \le a \le M$)가 부족 $b$($1 \le b \le M$, $a \ne b$)에 적대적이 되면, 부족 $a$의 모든 드래곤이 부족 $b$의 모든 드래곤을 향해 불덩이를 쏜다. 불덩이는 목표를 향해 곧게 날아가며, 목표에 도달한 뒤에도 같은 방향으로 계속 날아간다. 따라서 불덩이의 궤적은 반직선이다.

드래곤의 불덩이가 도로와 교차하면 도로가 손상된다. 앞으로 일어날 수 있는 적대 관계가 $Q$개 주어진다. 각 적대 관계마다 도로와 교차하는 불덩이의 개수를 구한다.

첫 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. $N$은 드래곤의 수, $M$은 부족의 수이다.

이어지는 $N$개의 줄의 $i$번째 줄에는 정수 $A_i$, $B_i$, $C_i$가 주어진다. 이는 $i$번 드래곤이 $(A_i, B_i)$에 있고 부족 번호가 $C_i$라는 뜻이다.

다음 줄에는 정수 $D_1$, $E_1$, $D_2$, $E_2$가 주어진다. 두 마을은 각각 $(D_1, E_1)$과 $(D_2, E_2)$에 있다.

다음 줄에는 적대 관계의 수 $Q$가 주어진다.

이어지는 $Q$개의 줄의 $j$번째 줄에는 정수 $F_j$, $G_j$가 주어진다. 이는 $j$번째 적대 관계에서 부족 $F_j$가 부족 $G_j$에 적대적이 된다는 뜻이다.

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 적대 관계에서 도로와 교차하는 불덩이의 개수를 출력한다.

$2 \le N \le 30000$

$2 \le M \le N$

$-10^9 \le A_i, B_i \le 10^9$ ($1 \le i \le N$)

$1 \le C_i \le M$ ($1 \le i \le N$)

$-10^9 \le D_1, E_1, D_2, E_2 \le 10^9$

$N+2$개의 점 $(A_1, B_1), \ldots, (A_N, B_N), (D_1, E_1), (D_2, E_2)$는 모두 서로 다르고, 어느 세 점도 한 직선 위에 있지 않다.

$1 \le Q \le 100000$

$1 \le F_j, G_j \le M$이고 $F_j \ne G_j$이다.

쌍 $(F_j, G_j)$는 모두 서로 다르다.