题目描述

在 JOI 平原上，人们与龙共同生活。

JOI 平原是一个具有 $X$ 坐标和 $Y$ 坐标的广阔坐标平面。横坐标为 $x$、纵坐标为 $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 平原上，有两个位于点 $(D_1, E_1)$ 和 $(D_2, E_2)$ 的人类村落。两个村落之间由一条道路相连，该道路是连接两村位置的线段。

点 $(A_1, B_1), \dots, (A_N, B_N)$ 与点 $(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$。这表示 JOI 平原上有 $N$ 条龙，以及 $M$ 个龙族部落。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含三个以空格分隔的整数 $A_i$、$B_i$、$C_i$。这表示龙 $i$（$1 \le i \le N$）位于 JOI 平原上的点 $(A_i, B_i)$，其所属部落为 $C_i$。
• 下一行包含四个以空格分隔的整数 $D_1$、$E_1$、$D_2$、$E_2$。这表示两个位于 JOI 平原上点 $(D_1, E_1)$ 和 $(D_2, E_2)$ 的人类村落。
• 下一行包含一个整数 $Q$，表示可能发生的龙族部落冲突的数量。
• 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含两个以空格分隔的整数 $F_j$、$G_j$。这表示在第 $j$ 个可能的冲突中，部落 $F_j$ 对部落 $G_j$ 产生敌意。

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 个部落冲突中经过道路的火球数量。

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

1
2

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

1

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

4
2
4
0
2
1

提示

样例 1 解释

在第一次部落冲突中，满足以下条件：

• 龙 1 向龙 3 发射的火球不会经过道路。
• 龙 1 向龙 4 发射的火球不会经过道路。
• 龙 2 向龙 3 发射的火球会经过道路。
• 龙 2 向龙 4 发射的火球不会经过道路。

因此，有 1 个火球经过道路。

在第二次部落冲突中，满足以下条件：

• 龙 3 向龙 1 发射的火球会经过道路。
• 龙 3 向龙 2 发射的火球会经过道路。
• 龙 4 向龙 1 发射的火球不会经过道路。
• 龙 4 向龙 2 发射的火球不会经过道路。

因此，有 2 个火球经过道路。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 30000$。
• $2 \le M \le N$。
• $-1000000000 \le A_i \le 1000000000$（$1 \le i \le N$）。
• $-1000000000 \le B_i \le 1000000000$（$1 \le i \le N$）。
• $1 \le C_i \le M$（$1 \le i \le N$）。
• $-1000000000 \le D_1 \le 1000000000$。
• $-1000000000 \le E_1 \le 1000000000$。
• $-1000000000 \le D_2 \le 1000000000$。
• $-1000000000 \le E_2 \le 1000000000$。
• $N + 2$ 个点 $(A_1, B_1), \dots, (A_N, B_N), (D_1, E_1), (D_2, E_2)$ 互不相同，且任意三点不共线。
• $1 \le Q \le 100000$。
• $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 < k \le Q$）。

子任务

共有 3 个子任务。每个子任务的得分及额外约束如下：

子任务 1 [15 分]

• $N \le 3000$。

子任务 2 [45 分]

• $Q \le 100$。

子任务 3 [40 分]

无额外约束。

翻译由 Qwen3-235B 完成