blobblush

Time limit1sMemory limit1024 MB

Summary

Choose a subset of {1,...,N} whose XOR is maximum, then among those use the fewest cards, then the lexicographically smallest set, and output it sorted.

Level: Hard8 of 10
Topics: Bit manipulation, Greedy, Math, Combinatorics
Solved: No attempts yet

Problem

Cute baby Juhwan has number cards with the positive integers from $1$ to $N$ written on them.

Juhwan learns that today is the birthday of his best friend, baby Blob, and gives $K$ cards as a gift.

Juhwan chose the cards to satisfy the following conditions.

The XOR of all numbers on the chosen cards must be as large as possible. Here ⊕ denotes bitwise exclusive or (xor).
If there are multiple ways to choose cards satisfying the first condition, he must choose as few cards as possible.
If there are multiple ways to choose cards satisfying the second condition, he must choose the one that is lexicographically smallest.

Find $K$ and each number on the chosen cards.

Input

The first line gives $N$ .

Output

On the first line, print $K$ . $K$ is a positive integer no greater than $N$ .

Starting from the second line, print the positive integers on the $K$ chosen cards that satisfy the conditions, one per line in ascending order.

If there are multiple possible answers, print the lexicographically smallest one.

Constraints

$1 \leq N \leq 10^{18}$

Hint

A sequence A of length K is lexicographically smaller than a sequence B of the same length if there is an index i such that the 1st through (i-1)th elements of A equal those of B, and the i-th element of A is smaller than the i-th element of B.

Examples1

Example 1
Input
```
7
```
Expected output
```
1
7
```