Ринат и Ляйсан — два белых барса. Ринат давно хотел пригласить Ляйсан на свидание. Но оказалось, что найти подходящее время для встречи не так просто: у обоих очень необычные расписания.
Начиная с момента времени $$$0$$$, Ринат первые $$$a$$$ секунд свободен, следующие $$$a$$$ секунд занят, затем снова $$$a$$$ секунд свободен и так далее.
У Ляйсан расписание устроено наоборот: первые $$$b$$$ секунд она занята, следующие $$$b$$$ секунд свободна, затем снова $$$b$$$ секунд занята и так далее.
Чтобы пригласить Ляйсан на свидание, Ринату нужно найти момент, начиная с которого они оба будут свободны в течение хотя бы одной полной секунды.
Ринат готов ждать не дольше момента времени $$$T$$$.
Найдите минимальное целое число $$$t$$$ ($$$0 \le t \le T$$$), такое, что Ринат и Ляйсан оба свободны в течение всего промежутка $$$[t, t+1)$$$, то есть с момента $$$t$$$ включительно до момента $$$t+1$$$ не включительно.
Если такого момента не существует, выведите $$$-1$$$.
В первой строке даны три целых числа $$$a$$$, $$$b$$$ и $$$T$$$ ($$$1 \le a,b \le 10^{18}$$$, $$$0 \le T \le 10^{18}$$$).
Выведите минимальное целое число $$$t$$$, такое, что в течение всего промежутка времени $$$[t, t+1)$$$ Ринат и Ляйсан оба свободны.
Если такого $$$t$$$ не существует, выведите $$$-1$$$.
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы, всех тестов необходимых для неё групп и тестов из условия.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | |
| 1 | 15 | $$$T \le 10^6$$$ | – | |
| 2 | 15 | $$$a, b \le 10^3$$$ | – | |
| 3 | 10 | $$$b | lt; a$$$ | – |
| 4 | 15 | $$$b | lt; 2a$$$ | 3 |
| 5 | 15 | $$$b | lt; 1\,000\,001 \cdot a$$$ | 2–4 |
| 6 | 10 | $$$b$$$ делится на $$$a$$$ без остатка | – | |
| 7 | 20 | Нет дополнительных ограничений | 1–6 |
5 3 10
3
3 5 10
6
3 8 5
-1
В первом примере Ринат свободен в течение первых $$$5$$$ секунд, то есть на промежутке $$$[0,5)$$$, затем занят на $$$[5,10)$$$. Ляйсан, наоборот, занята на $$$[0,3)$$$ и свободна на $$$[3,6)$$$. Поэтому впервые они одновременно свободны на промежутке $$$[3,5)$$$, и минимальный подходящий момент равен $$$3$$$.
Во втором примере Ляйсан свободна на $$$[5,10)$$$. В момент $$$5$$$ Ринат ещё занят, так как его занятый промежуток — $$$[3,6)$$$. Начиная с момента $$$6$$$ он снова свободен, поэтому ответ равен $$$6$$$.
В третьем примере до момента $$$T=5$$$ подходящего момента нет: Ляйсан становится свободна только в момент $$$8$$$. Поэтому ответ равен $$$-1$$$.
