Нигде Деньги
В городе Nowhere люди используют "монеты и слоты" в качестве денег. Существует 2 типа монет: размер1 и размер2. Монета размер2 вдвое толще монеты размер1. Люди складывают свои монеты в слоты и используют их как деньги. Существует множество размеров слотов. Слот размера n может вместить n монет размер1. Только полностью заполненный слот считается легальной валютой. Стоимость каждого заполненного слота определяется уникальными способами, которыми можно сложить монеты внутри. Например, для слота размером 1 существует только один способ положить одну монету размер1 внутрь. Для слота размером 2 существует 2 способа: положить две монеты размер1 или одну монету размер2. А для слота размером 5 существует 8 способов сложить монеты, которые можно проиллюстрировать следующим образом: 1 1 1 1 1, 1 1 1 2, 1 1 2 1, 1 2 1 1, 2 1 1 1, 1 2 2, 2 1 2, 2 2 1. Таким образом, стоимость заполненного слота размером 1, 2 и 5 составляет 1, 2 и 8 (денежных) единиц соответственно (независимо от типа монет или способов их укладки).
Мистер Thinktwice является владельцем продуктового магазина в этом городе. Он заметил, что клиенты, скорее всего, пойдут в магазин, который может вернуть сдачу в форме, подходящей для их клиента. Из своего небольшого опроса он выяснил, что большинство клиентов хотели бы получить свою сдачу в форме, соответствующей этим 2 простым ограничениям:
Количество слотов должно быть минимальным.
Размер каждого слота должен отличаться от других как минимум на 2.
Это означает, что клиенты не хотят слоты одного размера, и им будет легче различать эти различия, если размеры не будут слишком близкими.
Поэтому мистер Thinktwice просит вас написать программу, которая может предоставить ему ряд размеров слотов для заданной суммы сдачи в соответствии с предыдущими ограничениями. Более того, ряд должен быть отсортирован в порядке убывания. Более конкретно, любая сумма сдачи может быть записана в этой формуле:
где
X — это сумма сдачи.
n — общее количество слотов.
s_i — размер i-го слота.
T — функция, отображающая размер слота в количество уникальных способов укладки монет.
и когда j ≫ k ≡ j ≥ k+2
Например:
Входные данные
Входные данные — это стандартный ввод, содержащий набор целых чисел. Каждая строка ввода — это сумма сдачи, представленная положительным целым числом, не превышающим 5000000000000000000 или 5×10^18. Ввод завершается, когда достигается EOF (конец файла).
Выходные данные
Для каждой суммы сдачи сгенерируйте 4 строки выходных данных. Первая строка — это сама сумма сдачи. Вторая строка — это ряд размеров слотов (в порядке убывания), разделенных пробелами. (Максимальный размер слота не превышает 90.) Третья строка — это ряд соответствующих значений слотов. Четвертая строка — пустая строка.