F. Упорядочивание рабочего стола
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваш друг Иван попросил вас помочь упорядочить его рабочий стол. Рабочий стол может быть представлен как прямоугольная матрица размера $$$n \times m$$$, состоящая из символов '.' (пустая клетка рабочего стола) и '*' (иконка).

Рабочий стол называется хорошим, если все его иконки находятся на каком-то префиксе столбцов и, возможно, префиксе следующего столбца (и не существует иконок за пределами данной фигуры). Другими словами, какое-то количество первых столбцов будет заполнено иконками, а также, возможно, какое-то количество первых клеток следующего (после последнего полного столбца) столбца будет также заполнено иконками (и все иконки на рабочем столе будут принадлежать этой фигуре). Это выглядит довольно похоже на расположение иконок на рабочем столе в реальной жизни.

За один ход вы можете взять одну иконку и передвинуть ее в любую пустую клетку рабочего стола.

Иван любит добавлять иконки на свой рабочий стол, а также удалять их, поэтому он просит вас ответить на $$$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$$$ запросов.

Примеры
Входные данные
4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2
Выходные данные
3
4
4
3
4
5
5
5
Входные данные
2 5 5
*...*
*****
1 3
2 2
1 3
1 5
2 3
Выходные данные
2
3
3
3
2