만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

별 세기

시간 제한6초메모리 제한1024 MB

요약
시간이 지나면서 별이 추가되고, 세 별을 꼭짓점으로 하는 삼각형 안과 변 위에 있는 별 아름다움의 합을 질의마다 구합니다.
난이도

어려움10점 중 8점

유형
기하, 분할 정복, 정렬
정답자
아직 제출이 없습니다

문제

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

별자리는 별 3개를 꼭짓점으로 하는 삼각형의 변 위와 내부에 있는 별들을 뜻한다. 별자리의 아름다움은 별자리에 속한 별들의 아름다움을 모두 더한 값으로 정한다.

Q1+Q2Q_1+Q_2일 동안 천체관측을 진행했다. 각 날마다 다음 두 가지 사건 중 하나가 일어났다.

  • (xi,yi)(x_i,y_i)에 아름다움이 cic_i인 별이 탄생한다. 현재 별의 개수를 MM이라 하면, 새 별은 별 M+1M+1로 이름 붙는다. 이 사건은 Q1Q_1번 일어난다.
  • 별 X,Y,ZX,Y,Z를 꼭짓점으로 하는 별자리를 관측한다. 이 사건은 Q2Q_2번 일어난다.

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

입력

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

이후 Q1+Q2Q_1+Q_2개의 줄에 사건이 주어진다. 각 줄의 첫 수는 사건의 종류 tt이다. t=1t=1이면 xix_i, yiy_i, cic_i가, t=2t=2이면 XX, YY, ZZ가 주어진다. (−109≤xi,yi≤109,1≤ci≤104,1≤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 현재 별의 개수))

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

출력

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

예제2

  1. 예제 1

    입력
    5 5
1 0 0 1
1 1 2 2
1 2 0 4
2 1 2 3
1 1 1 8
2 1 2 3
2 1 2 4
1 2 1 16
2 1 2 3
2 1 2 5
    예상 출력
    7 15 11 15 27

  2. 예제 2

    입력
    7 3
1 5 -1 3
1 -10 9 1
1 2 0 2
1 -7 -2 2
1 4 -3 1
2 1 2 4
1 7 4 3
2 4 5 6
1 -4 -7 3
2 2 6 7
    예상 출력
    8 8 9