JOI và IOI là đôi bạn thân. Một ngày nọ, hai bạn quyết định đến đài quan sát trên đỉnh núi để ngắm sao.

Từ đài quan sát có thể nhìn thấy \(N\) ngôi sao, được đánh số từ \(1\) đến \(N\). Mỗi ngôi sao có một trong ba màu: đỏ, xanh lam hoặc vàng.

Các ngôi sao được quan sát từ đây được biểu diễn bằng các điểm trên mặt phẳng tọa độ. Ngôi sao \(i\) (\(1 \le i \le N\)) tương ứng với điểm \(P_i(X_i,Y_i)\). Các điểm \(P_1,\ldots,P_N\) đôi một phân biệt và không có ba điểm nào thẳng hàng.

JOI và IOI quyết định tạo ra một chòm sao mang tên JOIOI. Trước tiên, hai bạn nghĩ đến việc dùng các tam giác nối ba ngôi sao, mỗi màu đỏ, xanh lam và vàng đúng một ngôi sao. Gọi một tam giác như vậy là tam giác tốt.

Hai bạn coi một cặp tam giác tốt không xét thứ tự là một phương án cho chòm sao JOIOI nếu thỏa mãn điều kiện sau:

• Hai tam giác tốt không có điểm chung, kể cả trên biên lẫn trong miền trong. Nói cách khác, hai tam giác không được chồng lên nhau, và cũng không được có một tam giác nằm trong tam giác còn lại.

Hình bên trái thỏa mãn điều kiện. Hai hình bên phải không thỏa mãn điều kiện.

JOI và IOI muốn đếm có bao nhiêu phương án cho chòm sao JOIOI. Lưu ý rằng ngay cả khi cùng sử dụng sáu ngôi sao, nếu cách nối chúng thành hai tam giác tốt khác nhau thì vẫn được tính là những phương án khác nhau.

Yêu cầu

Cho thông tin về các ngôi sao được quan sát từ đài quan sát, hãy viết chương trình tính tổng số phương án cho chòm sao JOIOI.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là số ngôi sao quan sát được.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa ba số nguyên \(X_i\), \(Y_i\), \(C_i\), cách nhau bởi dấu cách. Ngôi sao \(i\) nằm tại \(P_i(X_i,Y_i)\) và có màu được xác định bởi \(C_i\): \(0\) là đỏ, \(1\) là xanh lam, \(2\) là vàng.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên là tổng số phương án cho chòm sao JOIOI.

Ràng buộc

Mọi dữ liệu vào đều thỏa mãn:

• \(6 \le N \le 3\,000\).
• \(-100\,000 \le X_i \le 100\,000\).
• \(-100\,000 \le Y_i \le 100\,000\).
• \(0 \le C_i \le 2\).
• Có ít nhất một ngôi sao thuộc mỗi màu.
• \(P_i \ne P_j\) với mọi \(1 \le i < j \le N\).
• \(P_i\), \(P_j\), \(P_k\) không thẳng hàng với mọi \(1 \le i < j < k \le N\).

Phân nhóm

• Nhóm 1 (15 điểm): \(N \le 30\)
• Nhóm 2 (40 điểm): \(N \le 300\)
• Nhóm 3 (45 điểm): Không có ràng buộc bổ sung.

Ví dụ

7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2

4

8
16 0 0
17 0 0
0 7 2
0 -7 2
-1 -1 1
-1 1 2
-6 4 1
-6 -4 1

12

21
1 20 0
4 20 0
0 22 0
5 22 0
6 25 0
8 25 0
4 26 0
11 11 1
7 12 1
14 13 1
8 15 1
15 16 1
11 17 1
18 0 2
13 2 2
16 2 2
19 4 2
18 6 2
21 8 2
24 8 2
19 10 2

7748