시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB3612990.000%

문제

In the JOI plain, people are living with dragons. The JOI plain is a wide coordinate plane with X and Y coordinates. The point with X-coordinate x and Ycoordinate y is denoted by (x, y).

There are N dragons in the JOI plain, numbered from 1 to N. There are M tribes of dragons. The tribes are numbered from 1 to M. The dragon i (1 ≤ i ≤ N) is always staying at the point (Ai, Bi) in the JOI plain, and its tribe is Ci. It is not always the case that dragons of all kinds live in the JOI plain.

In the JOI plain, there are two villages of human beings at the points (D1, E1), (D2, E2). The two villages are connected by a road, which is a line segment connecting the two points of the villages.

The points (A1, B1), . . . , (AN, BN) and the points (D1, E1), (D2, E2) are different from each other. No three of them lie on a straight line.

Sometimes, there are conflicts between tribes of dragons. If the tribe a (1 ≤ a ≤ M) gets hostile to the tribe b (1 ≤ b ≤ M, a ≠ b), every dragon of tribe a launches balls of fire toward all dragons of tribe b. A ball of fire goes straight toward the target. After it gets to the target, it keeps going toward the same direction. Hence the track of a ball of fire is a half-line.

When conflicts between tribes occur, the road must be damaged if a ball of fire from a dragon comes across it. You have a list of Q possible conflicts between tribes of dragons which can occur in the near future. For each possible conflict, you want to calculate the number of balls of fire coming across the road.

Given the information of the dragons and the villages of human beings and a list of possible conflicts between tribes of dragons, write a program which calculates, for each conflict, the number of balls of fire coming across the road.

입력

Read the following data from the standard input.

  • The first line of input contains two space separated integers N, M. This means there are N dragons in the JOI plain, and there are M tribes of dragons.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains three space separated integers Ai, Bi, Ci. This means the dragon i (1 ≤ i ≤ N) is staying at the point (Ai, Bi) in the JOI plain, and its tribe is Ci.
  • The following line contains four space separated integers D1, E1, D2, E2. This means there are two villages of human beings at the points (D1, E1), (D2, E2) in the JOI plain.
  • The following line contains an integer Q, the number of possible conflicts between tribes of dragons.
  • The j-th line (1 ≤ j ≤ Q) of the following Q lines contains two space separated integers Fj, Gj. This means, in the j-th possible conflict, the tribe Fj gets hostile to the tribe Gj.

출력

Write Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) of output contains the number of balls of fire coming across the road in the j-th conflict between tribes.

제한

  • 2 ≤ N ≤ 30 000.
  • 2 ≤ M ≤ N.
  • −1 000 000 000 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • −1 000 000 000 ≤ Bi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Ci ≤ M (1 ≤ i ≤ N).
  • −1 000 000 000 ≤ D1 ≤ 1 000 000 000.
  • −1 000 000 000 ≤ E1 ≤ 1 000 000 000.
  • −1 000 000 000 ≤ D2 ≤ 1 000 000 000.
  • −1 000 000 000 ≤ E2 ≤ 1 000 000 000.
  • The N + 2 points (A1, B1), . . . , (AN, BN), (D1, E1), (D2, E2) are different from each other. No three of them lie on a straight line.
  • 1 ≤ Q ≤ 100 000.
  • 1 ≤ Fj ≤ M (1 ≤ j ≤ Q).
  • 1 ≤ Gj ≤ M (1 ≤ j ≤ Q).
  • Fj ≠ Gj (1 ≤ j ≤ Q).
  • (Fj, Gj) ≠ (Fk, Gk) (1 ≤ j < k ≤ Q).

서브태스크

번호배점제한
115

N ≤ 3 000.

245

Q ≤ 100.

340

There are no additional constraints.

예제 입력 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

In the first conflict between tribes, the following are satisfied:

  • The ball of fire launched by the dragon 1 toward the dragon 3 does not come across the road.
  • The ball of fire launched by the dragon 1 toward the dragon 4 does not come across the road.
  • The ball of fire launched by the dragon 2 toward the dragon 3 comes across the road.
  • The ball of fire launched by the dragon 2 toward the dragon 4 does not come across the road.

Hence one ball of fire comes across the road.

In the second conflict between tribes, the following are satisfied:

  • The ball of fire launched by the dragon 3 toward the dragon 1 comes across the road.
  • The ball of fire launched by the dragon 3 toward the dragon 2 comes across the road.
  • The ball of fire launched by the dragon 4 toward the dragon 1 does not come across the road.
  • The ball of fire launched by the dragon 4 toward the dragon 2 does not come across the road.

Hence two balls of fire come across the road.

예제 입력 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

채점 및 기타 정보

  • 예제는 채점하지 않는다.