Ира и Юля соскучились в ожидании Нового Года решили поразвлекаться с раскраской окна.

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

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

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

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

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

Формат входных данных

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

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

Формат выходных данных

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

Пример