A Segment and Triangles

Two distinct points $P,Q$ and $N$ distinct points $A_1,A_2,\cdots,A_N$ are given on the two-dimensional plane. All $N+2$ points are at distinct positions, and no three of them are collinear.

Choose three points $A_i,A_j,A_k$ with $1 \le i < j < k \le N$. The positional relationship between the triangle formed by these points and the segment $PQ$ is exactly one of the following four types.

• Type 1: The segment $PQ$ is completely contained in the interior of the triangle.
• Type 2: The segment $PQ$ intersects the boundary of the triangle exactly once.
• Type 3: The segment $PQ$ intersects the boundary of the triangle exactly twice.
• Type 4: The segment $PQ$ and the triangle are disjoint.

For every triangle that can be formed, count how many triangles have each type of relationship.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $X_P\ Y_P\ X_Q\ Y_Q$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$

The coordinates of $P$ and $Q$ are $(X_P,Y_P)$ and $(X_Q,Y_Q)$, respectively. The coordinates of $A_i$ are $(x_i,y_i)$.

For each test case, print one line containing four integers separated by spaces: the numbers of triangles of Type 1, Type 2, Type 3, and Type 4, in this order.

• $1 \le T \le 50\,000$.
• $3 \le N \le 200\,000$.
• The sum of $N$ over all test cases does not exceed $200\,000$.
• $-10^9 \le X_P,Y_P,X_Q,Y_Q \le 10^9$.
• $-10^9 \le x_i,y_i \le 10^9$ ($1 \le i \le N$).
• The $N+2$ points in each test case are pairwise distinct.
• No three of the $N+2$ points in a test case are collinear.