JOI and IOI are best friends. One day, they decided to observe the stars from an observatory on top of a mountain.

At the observatory, they can observe $N$ stars. Each star is numbered from $1$ to $N$, and each star is colored either red, blue, or yellow.

The stars observed at the observatory are represented as points on a coordinate plane. In this coordinate plane, the point corresponding to star $i$ ($1 \le i \le N$) is $P_i(X_i, Y_i)$. All points $P_1, \dots, P_N$ are distinct, and no three points among $P_1, \dots, P_N$ are collinear.

JOI and IOI decided to create a constellation called the "JOIOI Constellation." First, they thought of using a triangle formed by connecting three stars: one red, one blue, and one yellow. Such a triangle is called a "good triangle."

They decided that a candidate for the JOIOI Constellation would be a pair of two good triangles (the order does not matter) that satisfy the following condition:

• The two good triangles (including their boundaries and interiors) have no common points. That is, the two good triangles do not overlap, and neither is contained within the other.

JOI and IOI decided to count how many such candidates for the JOIOI Constellation exist. Note that even if the six stars forming the candidates for the JOIOI Constellation are the same, if the way the good triangles are formed is different, they are counted as different candidates.

Input

Read the following data from standard input:

• The first line contains an integer $N$, representing the number of stars observed at the observatory.
• The following $N$ lines, the $i$-th line ($1 \le i \le N$), contains three integers $X_i, Y_i, C_i$ separated by spaces. This indicates that the coordinates of star $i$ are $P_i(X_i, Y_i)$ and $C_i$ represents the color of star $i$. The color of star $i$ is red if $C_i = 0$, blue if $C_i = 1$, and yellow if $C_i = 2$.

Output

Output the total number of candidates for the JOIOI Constellation as an integer on a single line.

Constraints

All input data satisfy the following conditions:

• $6 \le N \le 3000$.
• $-100\,000 \le X_i \le 100\,000$.
• $-100\,000 \le Y_i \le 100\,000$.
• $0 \le C_i \le 2$.
• There is at least one star of each color.
• $P_i \neq P_j$ ($1 \le i < j \le N$).
• $P_i, P_j, P_k$ are not collinear ($1 \le i < j < k \le N$).

Subtasks

Subtask 1 [15 points]

• $N \le 30$ is satisfied.

Subtask 2 [40 points]

• $N \le 300$ is satisfied.

Subtask 3 [45 points]

• No additional constraints.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

12

Input 3

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

Output 3

7748

Figure 1. A good triangle