Đồng bằng JOI là một mặt phẳng tọa độ. Có \(N\) con rồng, đánh số từ \(1\) đến \(N\), thuộc \(M\) bộ tộc. Rồng \(i\) đứng tại \((A_i,B_i)\) và thuộc bộ tộc \(C_i\). Không nhất thiết mọi bộ tộc đều có rồng.

Hai ngôi làng nằm tại \((D_1,E_1)\) và \((D_2,E_2)\), được nối bởi một con đường là đoạn thẳng giữa hai điểm đó. Toàn bộ \(N+2\) điểm nói trên đôi một khác nhau và không có ba điểm thẳng hàng.

Khi bộ tộc \(a\) thù địch bộ tộc \(b\), mỗi rồng của bộ tộc \(a\) phóng một quả cầu lửa về phía mỗi rồng của bộ tộc \(b\). Quả cầu đi thẳng qua mục tiêu và tiếp tục theo cùng hướng, nên quỹ đạo là một tia. Với mỗi trong \(Q\) xung đột có thể xảy ra, hãy đếm số quả cầu lửa cắt con đường.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i,C_i\).
• Dòng tiếp theo chứa \(D_1,E_1,D_2,E_2\).
• Dòng tiếp theo chứa \(Q\).
• \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(F_j,G_j\): bộ tộc \(F_j\) thù địch bộ tộc \(G_j\).

Dữ liệu ra

In \(Q\) dòng; dòng thứ \(j\) là số quả cầu lửa cắt con đường trong xung đột thứ \(j\).

Ràng buộc

• \(2\le N\le 30\,000\).
• \(2\le M\le N\).
• \(-10^9\le A_i,B_i,D_1,E_1,D_2,E_2\le 10^9\).
• \(1\le C_i\le M\).
• \(N+2\) điểm đôi một khác nhau; không có ba điểm thẳng hàng.
• \(1\le Q\le 100\,000\).
• \(1\le F_j,G_j\le M\) và \(F_j\ne G_j\).
• Các cặp có thứ tự \((F_j,G_j)\) đôi một khác nhau.

Phân nhóm

1. \(15\) điểm: \(N\le 3\,000\)
2. \(45\) điểm: \(Q\le 100\)
3. \(40\) điểm: Không có

Giới hạn

• Thời gian: 3 giây.
• Bộ nhớ: 256 MB.

Ví dụ

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

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 4, bài Dragon 2.