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

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

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

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

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

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

Входные данные

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

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

Выходные данные

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