Дана матрица, состоящая из \(n\) строк и \(m\) столбцов. Строки пронумерованы сверху вниз, столбцы пронумерованы слева направо.
Ячейки данной матрицы могут быть свободными или заблокированными.
Назовем путь в матрице лестницей, если он:
- начинается и заканчивается в свободной ячейке;
- посещает только свободные ячейки;
- имеет одну из двух возможных структур:
- вторая ячейка лежит на \(1\) справа от первой, третья — на \(1\) снизу от второй, четвертая — на \(1\) справа от третьей, и так далее;
- вторая ячейка лежит на \(1\) снизу от первой, третья — на \(1\) справа от второй, четвертая — на \(1\) снизу от третьей, и так далее.
В частности, путь, состоящий из одной ячейки, считается лестницей.
Некоторые примеры лестниц:
Изначально все ячейки в матрице свободные.
Требуется обработать \(q\) запросов, каждый из которых переключает состояние одной ячейки. То есть, если клетка в данный момент свободна, то делает ее заблокированной, а если заблокирована, то делает ее свободной.
После каждого запроса требуется вывести количество различных лестниц. Две лестницы считаются различными, если существует такая ячейка, которая входит в один путь и не входит в другой.
Выходные данные
Выведите \(q\) целых чисел — \(i\)-е число должно быть равно количеству различных лестниц в матрице после \(i\) запросов. Две лестницы считаются различными, если существует такая ячейка, которая входит в один путь и не входит в другой.