在 JOI 平原上，人们与龙共同生活。 JOI 平原是一个广阔的坐标平面，具有 $X$ 和 $Y$ 坐标。坐标为 $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 平原上，有两个人类村庄，分别位于点 $(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 \neq 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$ 种族群冲突中穿过道路的火球数量。

数据范围

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

• $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)$ 互不相同。其中任意三点都不在同一直线上。
• $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 \neq G_j$（$1 \le j \le Q$）。
• $(F_j, G_j) \neq (F_k, G_k)$（$1 \le j < 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

样例输入 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