*report_ru.md

Структуры данных

Военные учения 2

Ограничение времени	1 секунда
Ограничение памяти	64Mb
Ввод	стандартный ввод
Вывод	стандартный вывод

Вступление

В ходе недавних военных учений (более подробно эта история рассказана в задаче «Военные учения») министр обороны Советской Федерации товарищ Иванов имел возможность лично убедиться в блестящей боевой готовности солдат вверенной ему Советской Армии. Но одна вещь всё же продолжала беспокоить выдающегося военачальника. Прославленный генерал понимал, что была продемонстрирована лишь физическая подготовка солдат. Теперь настало время организовать очередные учения и проверить интеллектуальные способности личного состава.

Генерал Шульман, вновь назначенный ответственным за проведение учений, пожертвовал все выделенные деньги бедным и с чистой совестью лёг спать. Во сне генералу явился учебник по тактике и изложил схему, руководствуясь которой можно провести учения совершенно бесплатно.

Задача

В соответствии с этой схемой учения делятся на N раундов, в течение которых N солдат, последовательно пронумерованных от 1 до N, маршируют друг за другом по кругу, т.е. первый следует за вторым, второй за третьим, ..., N-1-й за N-м, а N-й за первым. В каждом раунде очередной солдат выбывает из круга и идёт чистить унитазы, а оставшиеся продолжают маршировать. В очередном раунде выбывает солдат, марширующий на K позиций впереди выбывшего на предыдущем раунде. В первом раунде выбывает солдат с номером K.

Разумеется, г-н Шульман не питал никаких надежд на то, что солдаты в состоянии сами определить очерёдность выбывания из круга. «Эти неучи даже траву не могут ровно покрасить», – фыркнул он и отправился за помощью к прапорщику Шкурко.

Формат ввода

Единственная строка содержит целые числа N (1 ≤ N ≤ 100000) и K (1 ≤ K ≤ N).

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

Вывести через пробел номера солдат в порядке их выбывания из круга.

Пример

IN                                          OUT

5 3                                         3 1 5 2 4

Белые полосы

Ограничение времени	1 секунда
Ограничение памяти	64Mb
Ввод	стандартный ввод
Вывод	стандартный вывод

У каждого неудачника в жизни бывают не только чёрные, но и белые полосы. Марсианин Вась-Вась отмечает в календаре, представляющем собой таблицу m × n, те дни, когда ему ужасно не повезло. Если Вась-Васю не повезло в j-й день i-й недели, то он закрашивает ячейку таблицы (i, j) в чёрный цвет. Все незакрашенные ячейки в таблице имеют белый цвет.

Будем называть отрезками жизни прямоугольники размером 1 × l либо l × 1. Белыми полосами Вась-Вась считает все максимальные по включению белые отрезки таблицы. А сможете ли Вы определить, сколько всего белых полос было в жизни Вась-Вася?

Формат ввода

Первая строка содержит целые числа m, n, k — размеры календаря и количество неудачных дней в жизни Вась-Вася (1 ≤ m, n ≤ 30000; 0 ≤ k ≤ 60000). В следующих k строках перечислены неудачные дни в виде пар (x_i, y_i), где x_i — номер недели, к которой относится неудачный день, а y_i — номер дня в этой неделе (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ n). Описание каждого неудачного дня встречается только один раз.

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

Выведите число белых полос в жизни Вась-Вася.

Пример 1

IN                                          OUT

3 5 4                                       8
1 1
1 5
2 2
3 3

Пример 2

IN                                          OUT

5 1 2                                       2
2 1
3 1