← 返回题目列表

Codeforces · 1674/F

F. 桌面重新排列

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

你的朋友 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$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m$$$) — 改变其状态的单元格的位置(如果此单元格之前包含图标,则删除此图标,否则此单元格中会出现图标)。

输出

打印 $$$q$$$ 整数。其中第 $$$i$$$ 应该是应用第一个 $$$i$$$ 查询后使桌面正常运行所需的最少移动次数。

示例

输入 #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