드래곤 길들이기 timer 2s memory 512MB

KOI 국에는 사람들이 드래곤과 함께 살아가고 있다. KOI국은 (x, y)로 표현될 수 있는 좌표평면이다.

또한, KOI국에는 N마리의 드래곤이 함께 살아가고 있는데, M개의 드래곤 부족이 있다. 각 부족은 1부터 M까지 번호가 붙어 있다. i번째 드래곤 (1 ≤ i ≤ N)은 KOI 국의 (Ai, Bi) 에 위치하며, 부족은 Ci이다. 꼭 모든 부족의 드래곤이 KOI국에 살고 있는 것은 아닐 수 있다.

KOI국에는 사람들이 살고 있는 두 마을 (D1, E1), (D2, E2)이 있으며, 이 두 마을은 직선 도로로 이어져 있다.

점  (A1, B1), . . . , (AN, BN)과 (D1, E1), (D2, E2) 은 서로 다르며, 어떠한 세 점도 일직선 위에 위치하지 않음이 보장된다.

가끔, 드래곤 부족 간의 전쟁이 일어난다. 만약 부족  Fj (1 ≤ Fj ≤ M)가 부족 Gj (1 ≤ Gj ≤ M, Fj ≠ Gj)에 전쟁을 선포하면 부족 a의 모든 드래곤이 부족 b의 모든 드래곤에게 화염구를 발사한다. 각 화염구는 시작점부터 목표점을 향해 일직선으로 움직이며, 목표물에 적중한 후에도 같은 방향으로 계속 움직여, 반직선을 이루게 된다.

전쟁이 일어날 때마다 도로와 화염구의 경로가 교차하면 그 도로는 파괴된다. 따라서 당신은 Q개의 전쟁 시나리오에 대하여 각각 도로와 교차하는 화염구의 개수를 구해야 한다.

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.

N + 2 개의 점 (A1, B1), . . . , (AN, BN), (D1, E1), (D2, E2) 은 모두 서로 다르며, 어떠한 세 점도 일직선 상에 위치하지 않는다.

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).