Муниципальная олимпиада 2018 Хабаровский край 9-11 класс

Задача E. Мытьё посуды ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	А. Усманов, Н. Гребенюк	Ограничение времени:	1 сек
Входной файл:	Стандартный вход	Ограничение памяти:	256 Мб
Выходной файл:	Стандартный выход
Максимальный балл:	100

Условие

Во время Войны Бесконечности Доктор Стрэндж стал просматривать варианты возможного будущего. Из четырнадцати миллионов победным оказался лишь один, а после победы Мстители устроили большую вечеринку.

Всего на вечеринку придёт $N$ Мстителей. Не волнуйтесь, остальные герои не погибли (это же Марвел), они уже успели отправиться на своё сольное спасение мира. Но новая напасть оказалась не за горами, и, возможно, она пострашнее Таноса — героям необходимо решить, кто пойдёт мыть посуду. К сожалению, перчатка бесконечности была уничтожена, поэтому помыть всю (или хотя бы половину) посуды щелчком пальцев не получится. Сложно только представить, к какой гражданской войне могла привести эта ситуация, если бы только один из героев не вспомнил про народный метод решения подобных проблем — считалочку.

Все герои встали в круг, они пронумерованы от $1$ до $N$ , $1$ и $N$ герой стоят рядом. После они начали отсчитывать $M$ человек (енотов, деревьев и т.д.) от первого героя. Герой, на котором закончился счет, покидал круг, и счет начинался по новой, от следующего героя в круге. И так до тех пор, пока в круге не остался бы один герой — ему-то и придётся спасать этот мир (или по крайней мере эту вечеринку) от грязной посуды.

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

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

Первая строка содержит два целых числа $N$ и $M$ — количество Мстителей на вечеринке и количество героев, которое будет отсчитываться по кругу, соответственно.

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

В единственной строке выведите ответ на задачу.

Ограничения

$1 \le N \le 3 \cdot 10^5$

$1 \le M \le 10^9$

Описание подзадач и системы оценивания

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

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача	Баллы	Дополнительные ограничения		Необходимые подзадачи
Подзадача	Баллы	$N$	$M$	Необходимые подзадачи
1	7	$1 \le N \le 10^2$	$1 \le M \le 10^2$
2	11	$1 \le N \le 10^4$	$1 \le M \le 10^4$	1
3	8	$1 \le N \le 10^4$	$1 \le M \le 10^9$	1-2
4	11	$1 \le N \le 3 \cdot 10^4$	$1 \le M \le 10^9$	1-3
5	9	$1 \le N \le 4 \cdot 10^4$	$1 \le M \le 10^9$	1-4
6	12	$1 \le N \le 6 \cdot 10^4$	$1 \le M \le 10^9$	1-5
7	9	$1 \le N \le 7 \cdot 10^4$	$1 \le M \le 10^9$	1-6
8	12	$1 \le N \le 10^5$	$1 \le M \le 10^9$	1-7
9	21	$1 \le N \le 3 \cdot 10^5$	$1 \le M \le 10^9$	1-8

Пояснения к примерам

В первом примере герои будут покидать круг в следующем порядке: $3, 1, 5, 2$ .

Примеры тестов

№	Стандартный вход	Стандартный выход
1	`5 3`	`4`
2	`6 3`	`1`
3	`100 33`	`48`