Weirdtree

고원의 마녀 아즈사가 이상한 나무로 가득한 정원을 발견했다. 그녀는 친구 라이카와 함께 이 정원을 돌보기로 했다.

정원은 1번부터 N번까지 번호가 매겨진 나무 N그루가 일렬로 늘어선 수열로 볼 수 있다. 각 나무는 음이 아닌 정수 높이를 가진다. 아즈사는 Q개의 항목으로 이루어진 일정표에 따라 시간을 보낸다. 항목은 다음 세 종류 중 하나이다.

첫째, 나무 자르기 단계는 $l$, $r$, $k$로 주어진다. 이 단계에서 아즈사는 다음 $k$일 동안 나무를 자른다. 하루에 한 번, 인덱스가 $l$ 이상 $r$ 이하인 나무 가운데 높이가 가장 큰 나무를 찾아 그 높이를 $1$ 줄인다. 가장 큰 높이를 가진 나무가 여럿이면 그중 가장 왼쪽 나무를 고른다. 가장 큰 높이가 $0$이면 그날은 아무 일도 일어나지 않는다.

둘째, 마법 단계는 $i$, $x$로 주어진다. 인덱스 $i$인 나무의 높이를 $x$로 바꾼다.

셋째, 나무 조사 단계는 $l$, $r$로 주어진다. 인덱스가 $l$ 이상 $r$ 이하인 나무들의 높이 합을 구한다.

여기서 '이상'과 '이하'는 양 끝을 포함한다. 예를 들어 1부터 5까지의 정수는 1, 2, 3, 4, 5이다.

• $1 \le N, Q \le 300\,000$
• cut, magic, inspect 함수는 모두 합쳐 정확히 Q번 호출됨이 보장된다.
• $1 \le i \le N$
• $0 \le x, k, h[i] \le 1\,000\,000\,000$
• $1 \le l \le r \le N$

첫 번째 단계에서 나무를 3일 동안 자르면, 각 날이 끝난 뒤 나무 높이는 차례로 1, 2, 2, 1, 2, 3; 1, 2, 2, 1, 2, 2; 1, 1, 2, 1, 2, 2이다. 이 값들의 합은 9이며, 이것이 두 번째 단계 조사의 답이다.

세 번째 단계에서 나무를 3일 동안 자르면, 각 날이 끝난 뒤 나무 높이는 차례로 1, 1, 1, 1, 2, 2; 0, 1, 1, 1, 2, 2; 0, 0, 1, 1, 2, 2이다. 이 값들의 합은 6이며, 이것이 네 번째 단계 조사의 답이다.

다섯 번째 단계에서 나무를 1000일 동안 자르면, 날마다 자른 뒤 높이는 0, 0, 0, 1, 2, 2가 된다. 높이가 0인 나무는 잘리지 않기 때문이다. 이 값들의 합은 5이며, 이것이 여섯 번째 단계 조사의 답이다.

일곱 번째 단계에서 첫 번째 나무를 높이 1000까지 키우면 나무 높이는 1000, 0, 0, 1, 2, 2가 된다. 이 값들의 합은 1005이며, 이것이 여덟 번째 단계 조사의 답이다.

아홉 번째 단계에서는 999일 동안 날마다 첫 번째 나무의 높이가 1씩 줄어든다. 단계가 끝나면 나무 높이는 1, 0, 0, 1, 2, 2가 된다. 앞의 다섯 값의 합은 4이며, 이것이 마지막 열 번째 단계 조사의 답이다.