Dragon 2
题号：NC53234
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2017 Day4 T3「ドラゴン 2 / Dragon 2」
在一个平面直角坐标系上有N条龙，编号为；龙有M支种族，编号为。
i号龙位于(A_i,B_i)，它属于种族C_i。有可能有些种族已经没有龙了。
JOI平原上有一条路，这条路可视为一条线段，端点坐标分别为(D_1,E_1)和(D_2,E_2)。
上文中提到的所有坐标互不相同，且没有三点共线。
不同种族的龙之间会发生冲突。现给出Q种冲突，每种冲突用两个整数F_j,G_j来描述，意为种族F_j敌视种族G_j。此时，种族F_j的每一条龙会向种族G_j的每一条龙发射一个火球。火球轨迹是一条射线，打到对方的龙身上后，火球会穿过龙，沿着刚才的方向继续飞行。保证此后种族F_j不会再次敌视种族G_j。
火球会烧坏道路。对于给出的Q种冲突，求其中有多少个火球会烧坏道路。

输入描述:

第一行有两个整数N,M，用空格分隔。
在接下来的N行中，第i行有三个整数A_i,B_i,C_i。
第N+2行有四个整数D_1,E_1,D_2,E_2，用空格分隔。
第N+3行有一个整数Q。
在接下来的Q行中，第j行有两个用空格分隔的整数F_j,G_j。

输出描述:

输出共Q行，每行一个整数，表示在第j种冲突之中，有多少个火球会烧坏道路。
示例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
2

说明

在第一种冲突中：
2号龙向3号龙发射的火球会烧坏道路。
1号龙向3号龙、1号龙向4号龙、2号龙向4号龙发射的火球不会烧坏道路。
在第二种冲突中：
3号龙向1号龙、3号龙向2号龙发射的火球会烧坏道路。
4号龙向1号龙、4号龙向2号龙发射的火球不会烧坏道路。
示例2

输入

复制 
3 2
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 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

输出

复制 
4
2
4
0
2
1

备注:

对于的数据，。
对于另外的数据，。
对于所有数据，，所有点的横坐标绝对值、纵坐标绝对值均，所有点互不相同，没有三点共线，

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2401