CF1674F.Desktop Rearrangement

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.

你的朋友 Ivan 请你帮他整理桌面。桌面可以表示为一个 $n \times m$ 的矩形矩阵，其中每个元素为字符 .（表示桌面的空单元格）或 *（表示一个图标）。

若桌面上所有图标恰好占据若干个完整的前列，以及可能占据紧随其后的下一列的前若干个单元格（且桌面上不存在该图形以外的图标），则称该桌面是“良好的”（good）。换言之，桌面最左侧的若干列将被图标完全填满，之后至多还有一列（即紧邻最后一列完整列的右侧一列）的顶部若干单元格也被图标占据（且桌面上所有图标均属于该图形）。这与现实中桌面图标的排列方式基本一致。

在一次操作中，你可以将一个图标移动到桌面任意一个空单元格中。

Ivan 喜欢往桌面上添加或删除图标，因此他请你回答 $q$ 个查询：每次查询在添加或删除一个图标后，使桌面变为“良好”状态所需的最少操作次数是多少？

注意：这些查询是永久生效的，会持续改变桌面的状态。

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).

输入的第一行包含三个整数 $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$（$1 \le x_i \le n$；$1 \le y_i \le m$），表示状态发生改变的单元格位置（若该单元格此前含有图标，则移除该图标；否则在该单元格中添加一个图标）。

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.

输出 $q$ 个整数。其中第 $i$ 个整数表示在执行前 $i$ 个查询后，使桌面变为“良好”状态所需的最少操作次数。