408687: GYM103262 B Деревья на аллее

Представим себе бесконечную аллею, которая идет вдоль оси $$$OX$$$ и начинается в точке $$$X=0$$$.

С каждой из сторон аллеи посажены деревья. С одной стороны деревья посажены в точках $$$A$$$, $$$A+B$$$, $$$A+2\cdot B$$$ и так далее, то есть в точках $$$A+N\cdot B$$$ для любого целого неотрицательного $$$N$$$. При этом $$$0 \leq A < B$$$. Аналогично, с другой стороны аллеи деревья посажены в точках $$$C$$$, $$$C+D$$$, $$$C+2\cdot D$$$ и так далее. При этом $$$0 \leq C < D$$$. Обратите внимание, что в некоторых точках может оказаться два дерева — по одному с каждой из сторон аллеи (см. пример 1).

Вася любит фотографировать деревья. Он хочет прогуляться по аллее и сфотографировать минимум $$$K$$$ деревьев. Однако, он может фотографировать дерево только если находится в одной точке с ним. Вася довольно ленив и хочет пройти вдоль аллеи наименьшее возможное расстояние. При этом он может начать движение в любой точке аллеи — он просто подъедет к ней на машине. Помогите Васе найти отрезок минимальной длины, который ему нужно пройти пешком, чтобы сфотографировать хотя бы $$$K$$$ деревьев.

В первой строке заданы 4 целых числа: $$$A, B, C$$$ и $$$D$$$, $$$0 \leq A < B \leq 10^9$$$, $$$0 \leq C < D \leq 10^9$$$.

Во второй строке задано одно натуральное число $$$K$$$, $$$1 \leq K \leq 10^9$$$.

Вывести два целых числа $$$L$$$ и $$$R$$$ — концы отрезка аллеи, который нужно пройти Васе. Отрезок должен содержать хотя бы $$$K$$$ деревьев и иметь минимальную возможную длину. Несмотря на то что аллея бесконечная, вам нужно найти такие числа $$$L$$$ и $$$R$$$, что $$$0 \leq L \leq R \leq 8\cdot 10^{18}$$$. Гарантируется, что среди оптимальных ответов существует ответ, удовлетворяющий этим ограничениям. Если таких оптимальных ответов несколько, можно вывести любой из них.

Подзадача 1, 25 баллов: все входные числа не превосходят $$$5000$$$.

Подзадача 2, 25 баллов: все входные числа не превосходят $$$10^7$$$.

Подзадача 3, 50 баллов: дополнительных ограничений нет.

1 2 3 5
4

1 5

0 2 1 2
6

1000 1005

В первом примере Вася может сфотографировать дерево в точке 1, два дерева в точке 3 и дерево в точке 5. Другой возможный оптимальный вариант — пройти от точки 5 до точки 9, длина пути так же будет равна 4. Более короткого маршрута, содержащего хотя бы 4 дерева, не существует.

Во втором примере в каждой точке находится ровно по одному дереву (с одной стороны деревья на четных позициях, с другой — на нечетных). Любой маршрут длины 5 будет содержать 6 деревьев.