#436 Dynamic Nonogram

Statement

Statement language

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=[A_1,A_2,\cdots,A_K],

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 , insert it at the beginning. If , insert it at the end.

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

Input

The input is given in the following format.

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

Output

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

Constraints

$1 \le W \le 10^{18}$ .
$1 \le Q \le 200\,000$ .

Subtasks

#	Score	Constraints
1	12	Every query `1 i X` has $X=1$ .
2	12	The sequence length never exceeds $1$ .
3	18	The sequence length never exceeds $100$ .
4	20	$Q \leq$ .

Samples

Sample 1

Input

Output

Sample 2

Input

Output