题目描述

有 $N$ 个单元格从左到右排列。最初，没有任何一个单元格里有方块。

你需要按顺序处理 $Q$ 个查询。每个查询是以下两种类型之一：

• 1 x：往左数第 $x$ 个单元格中放置 $1$ 个方块。然后，如果此时每一个单元格中都至少有 $1$ 个方块，则从每一个单元格中移除 $1$ 个方块；
• 2 y：输出当前拥有至少 $y$ 个方块的单元格数量。

输入格式

N Q
query_1
query_2
...
query_Q

每个查询 $\mathrm{query}_i$ 按以下格式之一给出：

1 x
2 y

输出格式

设第二种类型的查询总数为 $K$，按顺序输出 $K$ 行答案，第 $i$ 行表示第 $i$ 个第二种类型查询的答案。

输入示例 1

3 7
1 1
1 3
1 3
2 1
2 2
1 2
2 1

输出示例 1

2
1
1

示例 1 说明

$N=3$，初始所有单元格方块数为 $(0, 0, 0)$。依次处理查询：

• 1 1：第 $1$ 格 $+1$，存在空格，不进行额外操作，结果 $(1, 0, 0)$；
• 1 3：第 $3$ 格 $+1$，结果 $(1, 0, 1)$；
• 1 3：第 $3$ 格 $+1$，结果 $(1, 0, 2)$；
• 2 1：至少 $1$ 个方块的有第 $1, 3$ 格，输出 $2$；
• 2 2：至少 $2$ 个方块的只有第 $3$ 格，输出 $1$；
• 1 2：第 $2$ 格 $+1$，此时每格均 $\ge 1$，每格减 $1$，结果 $(0, 0, 1)$；
• 2 1：至少 $1$ 个方块的只有第 $3$ 格，输出 $1$。

约束条件

• $1 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• $1 \le x \le N$
• $1 \le y \le 3 \times 10^5$
• 所有输入值均为整数
• 至少存在一个第二种类型的查询