Codeforces Round 786 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

greedy

implementation

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Desktop Rearrangement

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYour 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.

Input

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

Output

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.

Examples

Input

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

Output

3 4 4 3 4 5 5 5

Input

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

Output

2 3 3 3 2

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 19:10:47 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|