题目描述

给定一个 $N \times N$ 的 01 矩阵。你的任务是编写程序 rectcnt，完成以下工作：

1. 计算所有边平行于矩阵边界、且内部只包含 0 的子矩形数量；
2. 处理若干次修改操作，每次把某个位置 $(i,j)$ 的值翻转：0 变 1，1 变 0；
3. 在初始状态以及每次修改之后，都重新输出只包含 0 的子矩形总数。

输入格式

第一行输入两个正整数 $N,Q$，分别表示矩阵大小和操作次数。

接下来 $N$ 行，每行一个长度为 $N$ 的仅由 0 和 1 组成的字符串，表示矩阵初始状态。

接下来 $Q$ 行，每行两个整数 $i,j$，表示把第 $i$ 行、第 $j$ 列的元素翻转。矩阵下标从 0 开始。

输出格式

输出 $Q+1$ 行：

• 第 1 行输出初始矩阵中只包含 0 的子矩形数量；
• 第 $k+1$ 行输出第 $k$ 次操作完成后的答案。

数据范围

• $1 \le N \le 1000$
• $1 \le Q \le 10000$

样例

输入

4 3
0001
0100
1000
0010
1 2
1 1
2 0

输出

29
23
31
45

样例解释

初始时：

• 有 $12$ 个 $1\times1$ 矩形；
• $6$ 个 $1\times2$ 矩形；
• $2$ 个 $1\times3$ 矩形；
• $6$ 个 $2\times1$ 矩形；
• $1$ 个 $2\times2$ 矩形；
• $2$ 个 $3\times1$ 矩形。

总数为：

第一次操作后：

• 有 $11$ 个 $1\times1$ 矩形；
• $5$ 个 $1\times2$ 矩形；
• $2$ 个 $1\times3$ 矩形；
• $4$ 个 $2\times1$ 矩形；
• $1$ 个 $3\times1$ 矩形。

总数为：

第二次操作后：

• 有 $12$ 个 $1\times1$ 矩形；
• $6$ 个 $1\times2$ 矩形；
• $2$ 个 $1\times3$ 矩形；
• $6$ 个 $2\times1$ 矩形；
• $1$ 个 $2\times2$ 矩形；
• $3$ 个 $3\times1$ 矩形；
• $1$ 个 $4\times1$ 矩形。

总数为：

第三次操作后：

• 有 $13$ 个 $1\times1$ 矩形；
• $7$ 个 $1\times2$ 矩形；
• $3$ 个 $1\times3$ 矩形；
• $1$ 个 $1\times4$ 矩形；
• $8$ 个 $2\times1$ 矩形；
• $3$ 个 $2\times2$ 矩形；
• $5$ 个 $3\times1$ 矩形；
• $2$ 个 $3\times2$ 矩形；
• $2$ 个 $4\times1$ 矩形；
• $1$ 个 $4\times2$ 矩形。

总数为：

子任务

对于某一子任务，只有当该子任务的所有测试点都正确时，才能获得该子任务的分数。