Nowhere Money

노웨어(Nowhere) 마을에서는 동전(coin)과 슬롯(slot)으로 이루어진 화폐를 쓴다. 동전은 크기 1과 크기 2 두 종류가 있으며, 크기 2 동전의 두께는 크기 1 동전의 정확히 두 배다. 사람들은 슬롯 안에 동전을 쌓고, 가득 채운 슬롯을 화폐로 사용한다.

슬롯에는 여러 크기가 있다. 크기가 $n$인 슬롯에는 크기 1 동전 $n$개와 같은 두께만큼 동전을 쌓을 수 있다. 오직 완전히 가득 찬 슬롯만 정당한 화폐로 인정된다.

가득 찬 슬롯의 가치(value)는 그 슬롯을 동전으로 채우는 서로 다른 방법의 수다. 예를 들어:

• 크기 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$ 화폐 단위다(가치는 슬롯의 크기에만 의존하며, 어떤 동전을 쓰는지나 배열 방식과는 무관하다). 크기가 $n$인 가득 찬 슬롯의 가치를 $T(n)$으로 쓴다.

Thinktwice 씨는 식료품점을 운영한다. 그는 손님들이 거스름돈을 편한 형태로 돌려주는 가게를 선호한다는 것을 알아챘고, 간단한 조사를 통해 손님들이 다음 두 규칙에 따라 슬롯으로 구성된 거스름돈을 원한다는 것을 알게 되었다.

1. 슬롯의 개수가 최소여야 한다.
2. 두 슬롯의 크기는 서로 적어도 $2$만큼 차이가 나야 한다. 즉 같은 크기나 바로 인접한 크기의 슬롯이 없어야 하며, 그래야 손님이 슬롯을 쉽게 구분할 수 있다.

주어진 거스름돈 금액에 대해, 이 규칙을 만족하는 슬롯 크기의 수열을 내림차순으로 출력하라. 모든 거스름돈 금액은 다음과 같이 나타낼 수 있다.

$$X = \sum_{i=1}^{n} T(s_i) = T(s_1) + \cdots + T(s_i) + \cdots + T(s_n), \qquad s_1 \gg s_2 \gg \cdots \gg s_n > 0$$

여기서

• $X$는 거스름돈 금액,
• $n$은 슬롯의 총 개수,
• $s_i$는 $i$번째 슬롯의 크기,
• $T$는 슬롯 크기를 그 가치(채우는 서로 다른 방법의 수)로 대응시키는 함수이며,
• $j \gg k$는 $j \ge k + 2$를 뜻한다.

예를 들어:

$$10 = T(5) + T(2) = 8 + 2$$

$$1{,}000{,}000 = T(29) + T(25) + T(23) + T(11) + T(9) = 832040 + 121393 + 46368 + 144 + 55$$

입력은 여러 개의 거스름돈 금액으로 이루어지며, 한 줄에 하나씩 주어진다. 각 금액은 $5 \times 10^{18}$ 이하의 양의 정수다. 입력은 파일의 끝(EOF)에서 종료된다.

각 거스름돈 금액마다 네 줄을 출력한다.

1. 거스름돈 금액 그 자체,
2. 슬롯 크기를 내림차순으로 공백 하나로 구분하여 출력(모든 슬롯 크기는 $90$ 이하),
3. 그에 대응하는 슬롯 가치를 같은 순서로 공백 하나로 구분하여 출력,
4. 빈 줄.