문제

하늘이는 $x$축과 평행한 수직선 모양의 땅에 나무 $N$그루를 심었다. 나무가 심어져 있는 위치는 모두 다르며, 나무의 두께는 무시할 수 있을만큼 얇다.

나무가 잘 자라기 위해서는 햇빛을 많이 받는 것이 중요하기 때문에, 하늘이는 각 나무에 그림자가 얼마나 지고 있는 지 알아보기로 했다.

태양은 현재 서쪽에 떠있고 햇빛이 지면과 기울기 $-1$를 이루며 평행하게 비추고 있다.

그림에서 오른쪽 나무 위에 생기는 그림자의 길이는 $2$이다.

이 때 하늘이는 아래 행위를 $Q$회 시행한다.

• $1\, x\, h$: 위치 $x$에 높이 $h$의 나무를 심는다.
• $2\, x$: $x$ 위치에 있는 나무를 뽑는다.

하늘이를 위해 초기 및 각 시행 직후에 각 나무 위에 생기는 그림자의 길이의 합을 구하시오. 모든 그림자를 합하는 것이 아닌 나무 위에 생기는 그림자만 합하는 것에 주의하자.

입력

첫째 줄에 $N$과 $Q$가 공백을 사이에 두고 주어진다. $(1\le N,Q\le 200\, 000)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 나무가 심어진 위치와 높이를 의미하는 두 정수 $X_i$, $H_i$가 공백을 사이에 두고 주어진다. $(-10^9\le X_i\le 10^9;$ $1\le H_i\le 10^9)$

$N+1$번째 줄부터 $Q$개의 줄에 걸쳐 하늘이가 시행한 행위를 나타내는 세 정수 $v_i,x_i,h_i$가 공백을 사이에 두고 주어진다. $v_i=1$이면 위치 $x_i$에 나무가 없으며, $v_i=2$이면 위치 $x_i$에 나무가 존재한다. $(v_i\in\{1,2\} ;$ $-10^9\le x_i\le 10^9;$ $1\le h_i\le 10^9;$ $1\le i\le Q)$

출력

$Q+1$개의 줄에 걸쳐 초기 및 각 시행 직후에 각 나무 위에 생기는 그림자의 길이의 합을 나타내는 정수를 출력한다.

제한

힌트