Binary Knockout

Time limit1sMemory limit128 MB

Summary

A coin game on a line: each coin may double its position or move one step right; the player unable to move loses. Find the k-th value of n where the second player wins.

Level: Hard9 of 10
Topics: Game theory, Math, Bit manipulation
Solved: No attempts yet

Problem

Two players play a game called binary knockout. It is played on a board of $n$ fields numbered from $1$ to $n$ . At the start every field holds exactly one pawn. The players move alternately.

A single move works as follows: pick a pawn on some field $i$ and move it to field $2^k i$ for any integer $k \ge 1$ , as long as that field exists (that is, $2^k i \le n$ ). If the destination field already held a pawn, the two pawns knock each other out and both are removed from the board.

A player who cannot make any move on their turn loses.

The first player moves first and the second player moves second. By choosing the board size $n$ carefully, the second player can be given a guaranteed winning strategy; this happens, for example, for boards of size $1$ , $10$ , and $11$ . List every board size on which the second player has a winning strategy in increasing order, and report the $k$ -th of them.

Input

The only line of input contains one integer $k$ ( $1 \le k \le 1\,000\,000\,000$ ).

Output

Output a single integer: the $k$ -th smallest board size on which the second player has a winning strategy.

Examples4

Example 1
Input
```
2
```
Expected output
```
10
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
3
```
Expected output
```
11
```
Example 4
Input
```
4
```
Expected output
```
34
```