В Байтландии появилась Золотая Окружность Жуколюбителей (сокращённо ЗОЖ) — маршрут, проходящий по \(n \cdot k\) городам, и, понятно, представляющий из себя окружность. Города пронумерованы по кругу от \(1\) до \(n \cdot k\), расстояние между соседними городами на окружности равно \(1\) км.
Сергей не любит жуков, а любит бургеры. Хорошо, что на окружности есть \(n\) ресторанов фастфуда, которые расположены в \(1\)-м, \((k + 1)\)-м, \((2k + 1)\)-м, и так далее, \(((n-1)k + 1)\)-м городах, то есть через каждые \(k\) км.
Сергей начал своё путешествие из какого-то города \(s\) и ехал по кругу, останавливаясь в городах через равные расстояния \(l\) км (\(l > 0\)), пока не остановился вновь в городе \(s\). Сергей забыл числа \(s\) и \(l\), но он помнит, что от города \(s\) расстояние до ближайшего фастфуда было равно \(a\) км, а из города, в котором он остановился, проехав первые \(l\) км из \(s\), расстояние до ближайшего фастфуда было равно \(b\) км. Сергей ехал всегда в одну и ту же сторону по кругу, но при измерении расстояния до фастфуда учитывал оба направления.
Теперь его интересуют два числа. Первое \(x\) — минимальное число остановок (не считая первой), которое мог сделать Сергей до того, как вновь оказался в \(s\). Второе число \(y\) — максимальное число остановок (не считая первой), которое мог сделать Сергей до того, как вновь оказался в \(s\).
Выходные данные
Выведите два целых числа \(x\) и \(y\).
Примечание
В первом примере бургерные стоят в городах \(1\) и \(4\), начальный город \(s\) мог располагаться в городах \(2\), \(3\), \(5\), \(6\). Следующий город на пути мог также располагаться в городах \(2, 3, 5, 6\). Переберём все попарные комбинации этих городов. Тогда, если и \(s\), и город первой остановки Сергея — это город \(2\) (например, \(l = 6\)), Сергей уже в первой остановке оказался в \(s\), значит, \(x = 1\). В остальных же парах, потребуется \(1, 2, 3\) или \(6\) ходов для того, чтобы вновь попасть в \(s\), значит, \(y = 6\).
Во втором примере Сергей оба раза был в городах с ресторанами фастфуда, значит \(l\) равно \(2\), \(4\) или \(6\). Отсюда \(x = 1\), \(y = 3\).
В третьем примере бургерная всего одна, значит, существует два различных варианта расположения \(s\) и первого города в маршруте: \((6, 8)\) и \((6, 4)\), тогда для первого варианта \(l = 2\), для второго \(l = 8\). В обоих случаях для попадания в \(s\) Сергею потребуется сделать по \(x=y=5\) остановок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1 1
|
1 6
|
|
2
|
3 2
0 0
|
1 3
|
|
3
|
1 10
5 3
|
5 5
|