Problem 2: Goats

On a vast plain, $N$ goats are scattered, grazing leisurely. No two goats are at the same location. Goats are lazy and do not move from their spots; they only occasionally rotate in place. In fact, these goats are all robots that cannot walk and can only rotate in place. Furthermore, the goats' noses can be lit up remotely using LEDs, and the goats' eyes are high-performance cameras, allowing the video captured by the cameras to be checked remotely in real-time and desired scenes to be saved. A goat's eye can see its own nose, and it also has a see-through function, so even if goats overlap, it is possible to determine how many there are. Additionally, the left-to-right field of view of the eyes is $180^\circ$, so they can see everything on the boundary.

Depending on the positions of the goats, there may be goats that can see $N$ goats at once, and in some cases, there may be goats that cannot see $N$ goats at once regardless of which direction they look. For example, when six goats are given from 0 to 5 as shown in the figure below, goat 5 can see all six goats at once, but goat 2 cannot see all six goats at once regardless of which direction it looks.

For a special experiment, we choose two different goats that can see $N$ goats at once, and one arbitrary goat from the remaining goats. The three selected goats light up their noses so that their positions can be identified from anywhere. We watch the video captured by the eyes of the three selected goats and save one scene for each goat where the three lit-up goats are visible on one screen. By looking at the three saved scenes one by one, we place a special mark on all goats that are within the boundary (including the boundary) of the three lit-up goats and the other two lit-up goats. This mark is for a special experiment, and the goal of this experiment is to find the number of goats that have been marked all three times out of the $N$ goats.

For example, if three goats are selected from the total of six goats and marked with red dots, the figure below shows the goats that have been specially marked based on each goat. (Of course, each figure is not the saved scene itself.) In this case, the number of goats marked all three times is 4.

You must implement the following two functions for the special experiment.

• void init( int x[], int y[] ): This function is called initially and only once. x and y are arrays (vectors) of size $N$. The $x$-coordinates of the goat positions are given as x[0..N-1], and the $y$-coordinates are given as y[0..N-1]. The position of the $i$-th goat ($0 \le i \le N-1$) is $(x[i], y[i])$.
• int count( int a, int b, int c ): Using the coordinates of the three given goats $(x[a], y[a])$, $(x[b], y[b])$, and $(x[c], y[c])$, calculate and return the number of goats that are marked all three times.

Implementation Details

You must submit a single file named goat.cpp. This file must contain the implementation of the following functions:

• void init( int x[], int y[] )
• int count( int a, int b, int c )

These functions must operate as described above. Of course, you may create other functions to use internally. The submitted code must not perform input/output or access other files.

Examples

The provided grader reads input in the following format:

• Line 1: $N$ $Q$ ($N$: number of goats, $Q$: number of queries)
• Next $N$ lines each: $x$ $y$ ($x$ and $y$ coordinates of the goat's position)
• Next $Q$ lines each: $a$ $b$ $c$ (indices of the three goats, $0 \le a, b, c \le N-1$)

The provided grader prints the number of goats satisfying the condition for each query, separated by lines.

Constraints

• $3 \le N \le 3,000$
• $1 \le Q \le 5 \times 10^6$
• All $x$ and $y$ coordinates of goats are $0$ or greater and $10^9$ or less.

Subtasks

• Subtask 1 [5 points]: $N \le 500$, $Q \le 10^5$, no three points are collinear.
• Subtask 2 [17 points]: $N \le 500$, $Q \le 10^5$.
• Subtask 3 [10 points]: $N \le 500$, no three points are collinear.
• Subtask 4 [8 points]: $N \le 500$.
• Subtask 5 [29 points]: No three points are collinear.
• Subtask 6 [31 points]: No additional constraints.

Examples

Input 1

6 3
0 0
1 1
2 2
4 3
0 2
2 0
0 5 2
1 3 4
4 1 5

Output 1

4
4
3

Note

The following shows the function calls and their results for Example 1 in order.