| Автор: | А. Усманов, Н. Гребенюк | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Во время Войны Бесконечности Доктор Стрэндж стал просматривать варианты возможного будущего. Из четырнадцати миллионов победным оказался лишь один, а после победы Мстители устроили большую вечеринку.
Всего на вечеринку придёт N Мстителей. Не волнуйтесь, остальные герои не погибли (это же Марвел), они уже успели отправиться на своё сольное спасение мира. Но новая напасть оказалась не за горами, и, возможно, она пострашнее Таноса — героям необходимо решить, кто пойдёт мыть посуду. К сожалению, перчатка бесконечности была уничтожена, поэтому помыть всю (или хотя бы половину) посуды щелчком пальцев не получится. Сложно только представить, к какой гражданской войне могла привести эта ситуация, если бы только один из героев не вспомнил про народный метод решения подобных проблем — считалочку.
Все герои встали в круг, они пронумерованы от 1 до N, 1 и N герой стоят рядом. После они начали отсчитывать M человек (енотов, деревьев и т.д.) от первого героя. Герой, на котором закончился счет, покидал круг, и счет начинался по новой, от следующего героя в круге. И так до тех пор, пока в круге не остался бы один герой — ему-то и придётся спасать этот мир (или по крайней мере эту вечеринку) от грязной посуды.
Требуется написать программу, которая по количеству Мстителей на вечеринке и числу M определит, кому придётся мыть посуду.
Первая строка содержит два целых числа N и M — количество Мстителей на вечеринке и количество героев, которое будет отсчитываться по кругу, соответственно.
В единственной строке выведите ответ на задачу.
1 ≤ N ≤ 3 ⋅ 105
1 ≤ M ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | |
|---|---|---|---|---|
| N | M | |||
| 1 | 7 | 1 ≤ N ≤ 102 | 1 ≤ M ≤ 102 | |
| 2 | 11 | 1 ≤ N ≤ 104 | 1 ≤ M ≤ 104 | 1 |
| 3 | 8 | 1 ≤ N ≤ 104 | 1 ≤ M ≤ 109 | 1-2 |
| 4 | 11 | 1 ≤ N ≤ 3 ⋅ 104 | 1 ≤ M ≤ 109 | 1-3 |
| 5 | 9 | 1 ≤ N ≤ 4 ⋅ 104 | 1 ≤ M ≤ 109 | 1-4 |
| 6 | 12 | 1 ≤ N ≤ 6 ⋅ 104 | 1 ≤ M ≤ 109 | 1-5 |
| 7 | 9 | 1 ≤ N ≤ 7 ⋅ 104 | 1 ≤ M ≤ 109 | 1-6 |
| 8 | 12 | 1 ≤ N ≤ 105 | 1 ≤ M ≤ 109 | 1-7 |
| 9 | 21 | 1 ≤ N ≤ 3 ⋅ 105 | 1 ≤ M ≤ 109 | 1-8 |
В первом примере герои будут покидать круг в следующем порядке: 3, 1, 5, 2.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|