네모네모 해결하기

너비가 $W$인 $1 \times W$ 격자가 있다. 격자의 칸은 왼쪽부터 $1,2,\cdots,W$의 번호가 붙어 있다. 각 칸은 색칠하거나 색칠하지 않을 수 있다.

색칠된 칸들로 이루어진 극대 연속 구간을 색칠된 컴포넌트라고 한다. 양의 정수 수열

에 대하여, 다음 조건을 모두 만족하는 색칠을 $A$에 대한 올바른 색칠이라고 한다.

• 색칠된 컴포넌트가 정확히 $K$개 존재한다.
• 색칠된 컴포넌트를 왼쪽부터 순서대로 보았을 때, $i$번째 컴포넌트의 크기는 $A_i$이다 ($1 \le i \le K$).

따라서 서로 다른 두 색칠된 컴포넌트 사이에는 색칠되지 않은 칸이 하나 이상 존재한다. $K=0$이면 모든 칸이 색칠되지 않은 경우만 올바른 색칠이다.

예를 들어 $W=10$, $A=[3,2]$일 때 다음은 올바른 색칠이다. 검은 칸은 색칠된 칸을 뜻한다. 왼쪽부터 색칠된 컴포넌트의 크기가 각각 $3$, $2$이고, 두 컴포넌트 사이에 색칠되지 않은 칸이 존재한다.

처음에 수열 $A$는 비어 있다. 다음 쿼리를 순서대로 처리한다.

• 1 i X: 현재 $A$의 길이를 $K$라고 하자. $A_i$와 $A_{i+1}$ 사이에 $X$를 삽입한다. $i=0$이면 맨 앞에, $i=K$이면 맨 뒤에 삽입한다.
• 2 q: $q$번 쿼리에서 삽입한 수를 현재 수열에서 제거한다.
• 3 W': 격자의 너비를 $W'$로 변경한다.

각 쿼리를 처리한 뒤, 현재 수열에 대한 모든 올바른 색칠에서 항상 색칠되어 있는 칸의 개수를 구하여라.

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

$W\ Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

각 쿼리는 다음 세 형식 중 하나이다.

$1\ i\ X$ $2\ q$ $3\ W'$

각 쿼리를 처리한 뒤, 현재 수열에 대한 모든 올바른 색칠에서 항상 색칠되어 있는 칸의 개수를 한 줄에 하나씩 출력한다.

• $1 \le W \le 10^{18}$.
• $1 \le Q \le 200\,000$.
• $1 \le X \le 10^{18}$.
• $1 \le W' \le 10^{18}$.
• 1 i X 쿼리에서 쿼리 처리 직전 수열의 길이를 $K$라고 할 때, $0 \le i \le K$이다.
• 2 q 쿼리에서 $1 \le q$이고, $q$번 쿼리는 아직 제거되지 않은 수를 삽입한 1번 쿼리이다.
• 각 쿼리를 처리한 뒤 올바른 색칠이 하나 이상 존재한다.