선분과 삼각형

2차원 평면 위에 서로 다른 두 점 $P,Q$와 서로 다른 $N$개의 점 $A_1,A_2,\cdots,A_N$이 주어진다. 이 $N+2$개의 점은 모두 서로 다른 위치에 있으며, 어떤 세 점도 한 직선 위에 놓여 있지 않다.

$1 \le i < j < k \le N$을 만족하는 세 점 $A_i,A_j,A_k$를 골라 만든 삼각형과 선분 $PQ$의 위치 관계는 다음 네 가지 중 정확히 하나이다.

• 관계 1: 선분 $PQ$가 삼각형의 내부에 완전히 포함된다.
• 관계 2: 선분 $PQ$가 삼각형의 변과 정확히 한 번 교차한다.
• 관계 3: 선분 $PQ$가 삼각형의 변과 정확히 두 번 교차한다.
• 관계 4: 선분 $PQ$와 삼각형이 만나지 않는다.

만들 수 있는 모든 삼각형에 대하여, 각 위치 관계에 해당하는 삼각형의 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

점 $P$의 좌표는 $(X_P,Y_P)$이고, 점 $Q$의 좌표는 $(X_Q,Y_Q)$이다. 점 $A_i$의 좌표는 $(x_i,y_i)$이다.

각 테스트 케이스마다 한 줄에 관계 1, 관계 2, 관계 3, 관계 4에 해당하는 삼각형의 개수를 순서대로 공백으로 구분하여 출력한다.

• $1 \le T \le 50\,000$.
• $3 \le N \le 200\,000$.
• 모든 테스트 케이스에 대한 $N$의 합은 $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$).
• 각 테스트 케이스의 $N+2$개 점은 모두 서로 다른 위치에 있다.
• 각 테스트 케이스의 $N+2$개 점 중 어떤 세 점도 한 직선 위에 놓여 있지 않다.