你的朋友 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