Dynamic Nonogram

There is a $1 \times W$ grid. Its cells are numbered $1,2,\cdots,W$ from left to right. Each cell may be colored or uncolored.

A maximal consecutive interval of colored cells is called a colored component. For a sequence of positive integers

a coloring is valid for $A$ if it satisfies all of the following conditions.

• There are exactly $K$ colored components.
• When the colored components are ordered from left to right, the size of the $i$-th component is $A_i$ ($1 \le i \le K$).

Thus, at least one uncolored cell must lie between every two consecutive colored components. If $K=0$, the only valid coloring has every cell uncolored.

Initially, the sequence $A$ is empty. Process the following queries in order.

• 1 i X: Let the current length of $A$ be $K$. Insert $X$ between $A_i$ and $A_{i+1}$. If $i=0$, insert it at the beginning. If $i=K$, insert it at the end.
• 2 q: Remove the value that was inserted by query $q$ from the current sequence.
• 3 W': Change the width of the grid to $W'$.

After each query, find the number of cells that are colored in every valid coloring for the current sequence.

The input is given in the following format.

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

Each query has one of the following three forms.

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

After each query, print on its own line the number of cells that are colored in every valid coloring for the current sequence.

• $1 \le W \le 10^{18}$.
• $1 \le Q \le 200\,000$.
• $1 \le X \le 10^{18}$.
• $1 \le W' \le 10^{18}$.
• In a query 1 i X, if the length of the sequence immediately before the query is $K$, then $0 \le i \le K$.
• In a query 2 q, $q \ge 1$, and query $q$ is an insertion query whose value has not been removed yet.
• After every query, at least one valid coloring exists.