Задача D. Дайте Пушкину сдачи ≡

Условие

В журнале "Квантик" был опубликован математический рассказ Бориса Дружинина "Дайте Пушкину сдачи". В нём описывалось решение в классе следующей задачи, придуманной одним из учеников:

"- Пушкин купил томик своих стихов, выпущенный к двухсотлетию со дня его рождения. Пушкин дал продавцу девять рублей и получил сдачу... Чего смеётесь? Сдачу он получил - рубли. Копеек никаких не было, только рубли, понятно? Теперь вопрос: сколько рублей стоит этот томик стихов?"

Обсуждая условие задачи, ребята выяснили, что у Пушкина в кармане были современные российские рубли - обычные монеты достоинством один, два и пять рублей. Последующие рассуждения привели к такому факту: если Пушкин получил сдачу, значит книга стоит от одного до восьми рублей. Далее ребята догадались, что за книгу в четыре рубля Пушкин не станет давать продавцу девять. Зачем ему давать и потом обратно получать одни и те же монеты?

Следующим умозаключением стало следующее: Пушкин не мог дать ни одной рублёвой монеты - он бы её себе оставил, и на томик стихов всё равно хватило бы. Значит, он дал продавцу 9 рублей только двойками и пятерками. А такой вариант только один: 9 = 2 + 2 + 5. Если бы томик стоил 7 рублей или меньше, Пушкин дал бы 2 + 5 = 7 рублей или меньше, а не 9. Тогда получается, что книга стоит восемь рублей.

Попробуйте решить обобщенную задачу: Пушкин купил томик своих стихов, передав продавцу n рублей и получив сдачу. Сколько может стоит книга? Пушкин не станет передавать продавцу банкноты или монеты, если может осуществить покупку без них. В кармане у Пушкина могут оказаться обычные российские монеты и банкноты, имеющие хождение в стране, достоинством в 1, 2, 5, 10, 50, 100, 200, 500, 1000, 2000 и 5000 рублей (копеек нет). Книга стоит натуральное число рублей.

Формат входных данных

Единственная строка входного файла содержит одно натуральное число n.

Формат выходных данных

Если стоимость книги определяется однозначно, то выведите одно натуральное число - её стоимость. В противном случае выведите через пробел два натуральных числа - минимальную и максимальную возможную стоимость книги.

Ограничения

4 ≤ n ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 4 ≤ n ≤ 20, получат не менее 20 баллов.

Решения, верно работающие при 4 ≤ n ≤ 100, получат не менее 40 баллов.

Пояснения к примерам

В первом примере рассуждения аналогичны рассуждениям в условии.

Во втором примере Пушкин мог дать продавцу три монеты по пять рублей (или две монеты - 10 и 5 рублей) и получить сдачу от одного до четырёх рублей. Тогда книга может стоить от 11 до 14 рублей.

Во третьем примере Пушкин мог дать продавцу одну банкноту в 200 рублей и получить любую сдачу от 1 до 199 рублей.

Примеры тестов

11

10

15

11 14

200

1 199