20563번 - Counting Stars

밤하늘을 2차원 좌표평면으로 생각했을 때, 별은 좌표평면 상의 점으로 나타낼 수 있으며, 각자 고유한 수치인 아름다움을 가진다.

별자리란 별 3개를 꼭짓점으로 한 삼각형의 변 위 및 내부의 별들을 뜻한다. 별자리의 아름다움은 별자리의 별들의 아름다움의 합으로 정의한다.

$Q_1+Q_2$일간 천체관측을 진행했다. 각 날마다 다음 두가지 사건 중 하나가 일어났다.

• $(x_i,y_i)$에 아름다움이 $c_i$인 별이 탄생한다. 현재 별의 개수를 $M$이라 했을 때, 새 별은 별 $M+1$로 명명한다. 이 사건은 $Q_1$번 일어난다.
• 별 $X,Y,Z$를 꼭짓점으로 하는 별자리를 관측한다. 이 사건은 $Q_2$번 일어난다.

별자리를 관측할 때마다 그 별자리의 아름다움을 구하는 프로그램을 작성해야 한다.

첫 줄에 $Q_1$과 $Q_2$가 공백으로 구분되어 주어진다. $(3 \leq Q_1 \leq 2\,000, 1 \leq Q_2 \leq 1\,000\,000)$

이후 $Q_1+Q_2$개의 줄에 걸쳐 사건들이 주어진다. 각 줄의 첫 수로는 사건의 종류 $t$가 주어진다. $t=1$이면 새 별이 탄생했다는 뜻이고, $t=2$이면 별자리를 관측한다는 뜻이다. 그 후 $t=1$이면 $x_i,y_i,c_i$가, $t=2$이면 $X,Y,Z$가 주어진다. $(-10^9 \leq x_i,y_i \leq 10^9, 1 \leq c_i \leq 10^4, 1 \leq X < Y < Z \leq$ 현재 별의 개수$)$

모든 사건이 끝난 후 한 직선 위에 세 별이 위치한 경우가 없는 입력만 주어진다.

별자리를 관측할 때마다 그 별자리의 아름다움을 구해, 공백으로 구분하여 출력한다.