28805번 - Покраска 다국어

Магни и Моди соскучились в ожидании битвы с Кратосом и решили поразвлекаться с раскраской.

Раскраска выглядит весьма необычно: она представляет собой прямоугольник $n \times m$, разделенный на $nm$ единичных квадратов. Строки раскраски пронумерованы целыми числами от $1$ до $n$, а столбцы --- от $1$ до $m$. Будем обозначать за $(a, b)$ клетку, расположенную на пересечении строки с номером $a$ и столбца с номером $b$.

Изначально прямоугольник имеет шахматную раскраску, а именно клетка $(a, b)$ покрашена в белый цвет, если число $a + b$ четно, и в черный цвет в противном случае.

Моди очень любит порядок. Он называет простотой раскраски минимальное количество клеток, которые необходимо перекрасить (то есть черную клетку сделать белой и наоборот), чтобы после этого можно было выбрать такое целое число $t$, что клетка $(a, b) $является черной, если $a \le t$, и белой в противном случае. Иными словами, простота раскраски --- это минимальное количество клеток, цвет которых нужно изменить, чтобы после этого можно было провести прямую вдоль стороны длины $m$, и все клетки до этой прямой были черными, а после этой прямой --- белыми.

Магни не так любит порядок, зато он любит творчество. Периодически он перекрашивает одну из клеток раскраски в противоположный цвет, то есть, если клетка была черная, меняет ее цвет на белый, и наоборот. После каждого такого изменения Моди становится интересно, какую прототу имеет получившаяся раскраска. Всего Магни сделал $q$ перекрашиваний, причем на $i$-м из них он перекрасил клетку $(a_i, b_i)$.

Так как Магни совершает свои действия очень быстро, Моди попросил вас написать программу, которая ему поможет.

Первая строка входных данных содержит два целых числа $n$ и $m$ --- размеры раскраски ($1 \le n \le 200\,000$, $1 \le m \le 10$). Вторая строка содержит единственное целое число $q$ --- количество перекрашиваний, которые совершил Магни ($1 \le q \le 200\,000$).

Каждая из последующих $q$ строк содержит два целых числа $a_i$ и $b_i$ --- координаты клетки, которая была перекрашена $i$-м действием ($1 \le a_i \le n$, $1 \le b_i \le m$).

Выведите $q$ строк: для каждого действия, совершенного Магни, выведите простоту раскраски после этого действия.