Baskin Robbins 31

Interview

Time limit1sMemory limit512 MB

Summary

Given the cap A, list every move limit n up to A for which the second player wins the Baskin Robbins game ending at 31 where calling 31 loses.

Level: Medium4 of 10
Topics: Game theory, Math, Implementation, Brute force
Solved: No attempts yet

Problem

In the Baskin Robbins game, players call the numbers from 1 to 31 in order, and on each turn a player may call 1, 2, or 3 consecutive numbers. The player who calls 31 loses. Sion and Minwoo decided to play the Baskin Robbins game, but the game is so well known that both of them knew the winning strategy. Sion, who has always been unlucky, lost rock-paper-scissors and gave up the first move to Minwoo, so if they play under the usual rules he is bound to lose. So Sion suggested changing the rule so that a player may call 1 or more and at most N consecutive numbers, and Minwoo agreed.

Print every n (1 ≤ n ≤ A) for which Sion can win the game.

Input

The first line gives A. (1 ≤ A ≤ 31)

Output

Print, one per line in increasing order, every n for which Sion can win the game.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
1
2
```