Никита известен тем, что он отлично знает школьную программу по математике и умеет решать линейные уравнения любого уровня сложности. Для того, чтобы заинтересовать юного математика, учитель написал на доске два целых числа $$$a$$$ и $$$b$$$ и дал школьнику следующую задачу.
Учитель разрешил Никите не более, чем $$$k$$$ раз выполнить одно из следующих действий:
Задача Никиты — выполнить разрешенные действия таким образом, чтобы максимизировать произведение двух полученных чисел. К сожалению, решить данную задачу самостоятельно школьнику не удалось, поэтому вам придется ему помочь.
Первая строка содержит одно целое число $$$a$$$ ($$$1 \le a \le 10^{18}$$$) — первое число, которое учитель записал на доске.
Вторая строка содержит одно целое число $$$b$$$ ($$$1 \le b \le 10^{18}$$$) — второе число, которое учитель записал на доске.
Третья строка содержит одно целое число $$$k$$$ ($$$0 \le k \le 10^{18}$$$) — максимальное количество действий, которое может выполнить Никита.
Так как максимальное произведение полученных чисел после выполнения не более, чем $$$k$$$ операций может быть достаточно большим, вам не нужно выводить его.
Вместо этого выведите два целых числа $$$c$$$ и $$$d$$$ — полученные числа, произведение которых максимально. Для выведенных чисел должно быть верно, что $$$c \ge a$$$, $$$d \ge b$$$ и $$$(c - a) + (d - b) \le k$$$.
В случае, если существует несколько оптимальных ответов, выведите любой из них.
Обратите внимание, что входные данные и ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Помимо тестов из условия, данная задача содержит 25 тестов, каждый из которых будет независимо оцениваться в 4 балла.
590
5 9
463
7 6
552
6 6
В первом примере $$$k = 0$$$, поэтому Никита не может выполнить ни одного действия с данными числами. Таким образом, максимальное произведение чисел, записанных на доске, равно $$$5 \cdot 9 = 45$$$.
Во втором примере можно, например, три раза увеличить первое число на единицу. Можно показать, что полученное произведение $$$7 \cdot 6 = 42$$$ является максимальным.
В третьем примере можно один раз увеличить первое число на единицу и один раз увеличить второе число на единицу. Получится произведение $$$6 \cdot 6 = 36$$$.
