← 返回题目列表

Codeforces · 1373/G

G. 棋子

中文机器翻译题面 查看原题

给您一个由 $$$n$$$ 行和 $$$n$$$ 列组成的棋盘。行从下到上编号,从 $$$1$$$ 到 $$$n$$$。列从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$x$$$ 列和第 $$$y$$$ 行交叉处的单元格表示为 $$$(x, y)$$$。此外,第 $$$k$$$ 列是特殊列。

最初,棋盘是空的。董事会有 $$$m$$$ 变动。在第 $$$i$$$ 次更改期间,一个棋子会从棋盘上添加或删除。如果我们能够按照以下规则将所有棋子移动到特殊列,则当前棋盘是好的:

- 单元格$$$(x, y)$$$中的棋子可以移动到单元格$$$(x, y + 1)$$$、$$$(x - 1, y + 1)$$$或$$$(x + 1, y + 1)$$$;
- 您可以根据需要进行任意多次此类动作;
- 棋子不能移出棋盘;
- 每个单元格不能包含多个棋子。

当前的主板可能并不总是好的。要修复此问题,您可以向板上添加新行。新行添加在顶部,i。 e.他们将有数字$$$n+1、n+2、n+3、\dots$$$。

每 $$$m$$$ 发生变化后,打印一个整数 — 为使棋盘正常运行而必须添加的最小行数。

输入

第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5; 1 \le k \le n$$$)——分别是棋盘的大小、特殊列的索引和变化的次数。

然后是 $$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) — 分别是列的索引和行的索引。如果单元格 $$$(x, y)$$$ 中没有 pawn,则向该单元格添加一个 pawn,否则 — 从该单元格中删除该 pawn。

输出

每次更改后打印一个整数 - 为使电路板正常运行而必须添加的最小行数。

示例

输入 #1

5 3 5
4 4
3 5
2 4
3 4
3 5

输出 #1

0
1
2
2
1