Дана матрица, состоящая из $$$n$$$ строк и $$$m$$$ столбцов. Строки пронумерованы сверху вниз, столбцы пронумерованы слева направо.
Ячейки данной матрицы могут быть свободными или заблокированными.
Назовем путь в матрице лестницей, если он:
- начинается и заканчивается в свободной ячейке;
- посещает только свободные ячейки;
- имеет одну из двух возможных структур:
- вторая ячейка лежит на $$$1$$$ справа от первой, третья — на $$$1$$$ снизу от второй, четвертая — на $$$1$$$ справа от третьей, и так далее;
- вторая ячейка лежит на $$$1$$$ снизу от первой, третья — на $$$1$$$ справа от второй, четвертая — на $$$1$$$ снизу от третьей, и так далее.
В частности, путь, состоящий из одной ячейки, считается лестницей.
Некоторые примеры лестниц:
Изначально все ячейки в матрице свободные.
Требуется обработать $$$q$$$ запросов, каждый из которых переключает состояние одной ячейки. То есть, если клетка в данный момент свободна, то делает ее заблокированной, а если заблокирована, то делает ее свободной.
После каждого запроса требуется вывести количество различных лестниц. Две лестницы считаются различными, если существует такая ячейка, которая входит в один путь и не входит в другой.
В первой строке записаны три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n, m \le 1000$$$; $$$1 \le q \le 10^4$$$) — размерности матрицы и количество запросов.
В каждой из следующих $$$q$$$ строк записаны два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x \le n$$$; $$$1 \le y \le m$$$) — описание очередного запроса.
Выведите $$$q$$$ целых чисел — $$$i$$$-е число должно быть равно количеству различных лестниц в матрице после $$$i$$$ запросов. Две лестницы считаются различными, если существует такая ячейка, которая входит в один путь и не входит в другой.
2 2 8 1 1 1 1 1 1 2 2 1 1 1 2 2 1 1 1
5 10 5 2 5 3 1 0
3 4 10 1 4 1 2 2 3 1 2 2 3 3 2 1 3 3 4 1 3 3 1
49 35 24 29 49 39 31 23 29 27
1000 1000 2 239 634 239 634
1332632508 1333333000
