ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1896. Военные учения 2.1

Ограничение времени: 0.5 секунды
Ограничение памяти: 6 МБ
Ограничение на язык: C, C++, Pascal

Вступление

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

Задача

В соответствии с этой схемой учения делятся на N раундов, в течение которых N солдат, последовательно пронумерованных от 1 до N, маршируют друг за другом по кругу, т.е. первый следует за вторым, второй за третьим, ..., (N−1)-й за N-м, а N-й за первым. В каждом раунде очередной солдат выбывает из круга и идёт чистить унитазы, а оставшиеся продолжают маршировать. В очередном раунде выбывает солдат, марширующий на K позиций впереди выбывшего на предыдущем раунде. В первом раунде выбывает солдат с номером K.
Разумеется, г-н Шульман не питал никаких надежд на то, что солдаты в состоянии сами определить очерёдность выбывания из круга. «Эти неучи даже траву не могут ровно покрасить», — фыркнул он и отправился за помощью к прапорщику Шкурко.

Исходные данные

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

Результат

Поскольку ответ — номера солдат в порядке их выбывания из круга — может быть большим, выведите единственное число: xor чисел |isi| для всех i от 1 до N, где si — номер солдата, выбывшего на i-м шаге.

Пример

исходные данныерезультат
5 3
2

Замечания

В примере порядок выбывания солдат из круга такой: 3 1 5 2 4.
Тогда ответ равен |1 − 3| xor |1 − 2| xor |5 − 3| xor |2 − 4| xor |4 − 5| = 2 xor 1 xor 2 xor 2 xor 1 = 2.
Автор задачи: Подготовил Максим Пивко