Тролль-автомобилист

Тролль Зумбагеш купил автомобиль! Теперь ему можно не ходить по маршруту, а ездить с комфортом. Но вот незадача - в наши края внезапно пришла зима...

Теперь Зумбагешу срочно требуется сменить колёса на своей машине с летних на зимние. Одно колесо крепится n болтами, болты расположены по кругу. Пронумеруем их по часовой стрелке от 0 до n-1. Один болт на каждом колесе - особый, называется "секретка". Будем считать, что секретка имеет номер s.

В руководстве по обслуживанию автомобиля Зумбагеш прочитал: "При закручивании болтов колеса закручивайте их с шагом через k болтов, передвигаясь по часовой стрелке, секретку закручивайте последней."

После этого он крепко задумался: а с какого по номеру болта нужно начинать процесс закручивания, чтобы закручивая каждый раз через k болтов по часовой стрелке, закрутить в итоге все, а последней закрутить секретку?

Input format В единственной строке содержится три числа через пробел n, k, s - общее число болтов, шаг, то есть через сколько болтов нужно закручивать и номер секретки. 3 ≤ n ≤ 1018, 0 ≤ k ≤ 1018, 0 ≤ s ≤ n-1. Гарантируется, что ответ существует, то есть найдется болт, начиная с которого можно, закручивая с шагом через k болтов по часовой стрелке, закрутить все болты, последним закрутив секретку.

Output format Вывести одно число - номер болта, начиная с которого можно, закручивая с шагом через k болтов по часовой стрелке, закрутить все болты, последним закрутив секретку.

Examples Input Output 5 1 4 1

На рисунке приведена схема закручивания для параметров из примера n = 5 , k = 1 и s = 4 . То есть для 5 болтов закрутить их все, перемещаясь каждый раз через 1 болт по часовой стрелке так, что последним будет закручен 4-й болт. Он обозначает секретку и закрашен красным. Видно, что начинать нужно с болта номер 1.

Подзадачи Подзадача Номера тестов Баллы Ограничения Необходимые подзадачи 0 (тесты из условия) 1 0
1 2-10 20 n, k ≤ 1000 0 2 11-20 20 n, k ≤ 105 0, 1 3 21-30 60 n, k ≤ 1018 0, 1, 2 Проверка этой задачи проводится по группам тестов. Это значит, что решение должно выдать правильный ответ для каждого теста группы — только в этом случае все баллы за эту подзадачу будут засчитаны проверяемому решению. Если хотя бы на один тест из группы будет дан неверный ответ, баллы, начисляемые проверяемой программе за эту подзадачу, равны 0. Помимо этого, баллы за подзадачу начисляются только в том случае, когда пройдены тесты всех необходимых для нее подзадач.