#P1854E. Game Bundles

    ID: 8625 Type: RemoteJudge 3000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 10 Uploaded By: Tags>brute forceconstructive algorithmsdpgreedymath*3000

Game Bundles

No submission language available for this problem.

Description

Rishi is developing games in the 2D metaverse and wants to offer game bundles to his customers. Each game has an associated enjoyment value. A game bundle consists of a subset of games whose total enjoyment value adds up to $60$.

Your task is to choose $k$ games, where $1 \leq k \leq 60$, along with their respective enjoyment values $a_1, a_2, \dots, a_k$, in such a way that exactly $m$ distinct game bundles can be formed.

The input is a single integer $m$ ($1 \le m \le 10^{10}$) — the desired number of game bundles.

The first line should contain an integer $k$ ($1 \le k \le 60$) — the number of games.

The second line should contain $k$ integers, $a_1, a_2, \dots, a_k$ ($1 \le a_1, a_2, \dots, a_k \le 60$) — the enjoyment values of the $k$ games.

Input

The input is a single integer $m$ ($1 \le m \le 10^{10}$) — the desired number of game bundles.

Output

The first line should contain an integer $k$ ($1 \le k \le 60$) — the number of games.

The second line should contain $k$ integers, $a_1, a_2, \dots, a_k$ ($1 \le a_1, a_2, \dots, a_k \le 60$) — the enjoyment values of the $k$ games.

4
722
1
4
20 20 20 20
15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1
60

Note

In the first sample, any subset of size $3$ is a game bundle. There are $4$ such subsets.