给定一个矩阵,由 $$$n$$$ 行和 $$$m$$$ 列组成。行从上到下编号,列从左到右编号。
矩阵的每个单元格可以是空闲的或锁定的。
如果满足以下条件,我们将矩阵中的路径称为楼梯:
- 在空闲单元中开始和结束;
- 仅访问空闲单元格;
- 具有以下两个结构之一:第二个单元格位于第一个单元格右侧 $$$1$$$ 处,第三个单元格位于第二个单元格底部 $$$1$$$ 处,第四个单元格位于第三个单元格右侧 $$$1$$$ 处,依此类推; 第二个单元格距第一个单元格底部 $$$1$$$,第三个单元格距第二个单元格右侧 $$$1$$$,第四个单元格距第三个单元格底部 $$$1$$$,依此类推。
特别是,由单个单元格组成的路径被认为是楼梯。
以下是楼梯的一些示例:
最初矩阵的所有单元都是空闲的。
您必须处理 $$$q$$$ 查询,每个查询都会翻转单个单元格的状态。因此,如果单元格当前空闲,则将其锁定;如果单元格当前锁定,则将其锁定。
每次查询后打印不同楼梯的数量。如果存在这样一个单元格,它出现在一条路径中而没有出现在另一条路径中,则认为两个楼梯是不同的。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 1000$$$; $$$1 \le q \le 10^4$$$) — 矩阵的大小和查询的数量。
接下来的 $$$q$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x \le n$$$; $$$1 \le y \le m$$$) - 每个查询的描述。
输出
打印 $$$q$$$ 整数 - 第 $$$i$$$ 值应等于 $$$i$$$ 查询后不同楼梯的数量。如果存在这样一个单元格,它出现在一条路径中而没有出现在另一条路径中,则认为两个楼梯是不同的。
示例
输入 #1
2 2 8 1 1 1 1 1 1 2 2 1 1 1 2 2 1 1 1
输出 #1
5 10 5 2 5 3 1 0
输入 #2
3 4 10 1 4 1 2 2 3 1 2 2 3 3 2 1 3 3 4 1 3 3 1
输出 #2
49 35 24 29 49 39 31 23 29 27
输入 #3
1000 1000 2 239 634 239 634
输出 #3
1332632508 1333333000