Desktop Rearrangement

题意翻译

### 题目描述 Ivan 让你帮他重新安排他的桌面。桌面可以表示为一个大小为 $n \times m$ 的矩形矩阵，由字符 "." （表示桌面的空单元格）和 "*" （表示图标）组成。 如果桌面上的所有图标都占据一些完整列的前缀，并且可能占据下一列的前缀（并且在该图之外没有图标），则该桌面是"良好"的。 换句话说，一些列将被图标填充，并且下一列（在最后一个完整列之后）的一些单元格也将被图标填充（并且桌面上的所有图标都属于这个图），则该桌面是"良好"的。 这与现实生活中的图标排列几乎相同。 在一次移动中，你可以将一个图标移动到桌面上的任何空白单元格。 Ivan 喜欢在他的桌面上添加一些图标或将其删除，因此他要求你回答 $q$ 个问题：添加或删除一个图标后，使桌面变得良好所需的最少移动次数是多少？ 请注意，查询是永久性的，会更改桌面的状态。 ### 输入格式 输入的第一行包含三个整数 $n$, $m$ 和 $q$ $(1 \le n, m \le 1000; 1 \le q \le 2 \cdot 10^5)$，分别表示桌面中的行数、桌面中的列数和查询数。 接下来的 $n$ 行表示对桌面的布局。第 $i$ 行包含 $m$ 个字符 "." 和 "*" ——桌面第 $i$ 行的布局。 接下来的 $q$ 行表示查询。其中第 $i$ 行包含两个整数$x_i$, $y_i$ ——改变其单元格的状态（如果此单元格之前包含图标，则此图标将被删除，否则此单元格中会出现图标）。 ### 输出格式 输出 $q$ 个整数。第 $i$ 个整数应该是在前 $i-1$ 个查询后，使桌面"良好"所需的最小移动次数。

题目描述

Your friend Ivan asked you to help him rearrange his desktop. The desktop can be represented as a rectangle matrix of size $ n \times m $ consisting of characters '.' (empty cell of the desktop) and '\*' (an icon). The desktop is called good if all its icons are occupying some prefix of full columns and, possibly, the prefix of the next column (and there are no icons outside this figure). In other words, some amount of first columns will be filled with icons and, possibly, some amount of first cells of the next (after the last full column) column will be also filled with icons (and all the icons on the desktop belong to this figure). This is pretty much the same as the real life icons arrangement. In one move, you can take one icon and move it to any empty cell in the desktop. Ivan loves to add some icons to his desktop and remove them from it, so he is asking you to answer $ q $ queries: what is the minimum number of moves required to make the desktop good after adding/removing one icon? Note that queries are permanent and change the state of the desktop.

输入输出格式

输入格式

The first line of the input contains three integers $ n $ , $ m $ and $ q $ ( $ 1 \le n, m \le 1000; 1 \le q \le 2 \cdot 10^5 $ ) — the number of rows in the desktop, the number of columns in the desktop and the number of queries, respectively. The next $ n $ lines contain the description of the desktop. The $ i $ -th of them contains $ m $ characters '.' and '\*' — the description of the $ i $ -th row of the desktop. The next $ q $ lines describe queries. The $ i $ -th of them contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i \le n; 1 \le y_i \le m $ ) — the position of the cell which changes its state (if this cell contained the icon before, then this icon is removed, otherwise an icon appears in this cell).

输出格式

Print $ q $ integers. The $ i $ -th of them should be the minimum number of moves required to make the desktop good after applying the first $ i $ queries.

输入输出样例

输入样例 #1

4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2

输出样例 #1

3
4
4
3
4
5
5
5

输入样例 #2

2 5 5
*...*
*****
1 3
2 2
1 3
1 5
2 3

输出样例 #2

2
3
3
3
2