Problem: We will call a string x good if it satisfies the following condition:

* Condition: x can be represented as a concatenation of two copies of another string y of length at least 1.



For example, `aa` and `bubobubo` are good; an empty string, `a`, `abcabcabc` and `abba` are not good.

Eagle and Owl created a puzzle on good strings. Find one string s that satisfies the following conditions. It can be proved that such a string always exists under the constraints in this problem.

* 1 ≤ |s| ≤ 200
* Each character of s is one of the 100 characters represented by the integers 1 through 100.
* Among the 2^{|s|} subsequences of s, exactly N are good strings.

Constraints

* 1 ≤ N ≤ 10^{12}

Input

Input is given from Standard Input in the following format:


N


Output

In the first line, print |s|, the length of s. In the second line, print the elements in s in order, with spaces in between. Any string that satisfies the above conditions will be accepted.

Examples

Input

7


Output

4
1 1 1 1


Input

299


Output

23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

Solution (in PYTHON):

Solution:
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))

INF = 2147483647


import sys
stdin = sys.stdin

from copy import deepcopy
def makeTable(init, *dims):
    if 0 == len(dims): return deepcopy(init)
    return [makeTable(init, *dims[1:]) for i in xrange(dims[0])]


pascal = makeTable(None, 200, 200)

def choose(n, k):
    if k < 0 or k > n:
        return 0
    if 0 == k or n == k:
        return 1
    if None is not pascal[n][k]:
        return pascal[n][k]

    rr = choose(n-1, k-1) + choose(n-1, k)
    pascal[n][k] = rr

    return rr



N =        int( stdin.readline().strip() )


rr = []

basis = []
for i in range(2, 30):
    here = (1 << (i-1)) - 1
    basis.append((here, [1] * i))

    for second in range(1, i+1):
        here = (1 << (i + second - 1)) - 1
        extra = 0
        for length in range(1, second+1):
            extra += choose(second, length) * choose(i, length)
        for bs in range(1, 15):
            mult = 0
            for bl in range(1, bs+1):
                mult += choose(bs, bl)**2
            basis.append((here+extra*mult + (1 << (bs*2-1))-1, [1] * i + [2]*bs + [1] * second + [2]*bs))


basis.sort()
basis.reverse()
offset = 0
for h, pattern in basis:
    while h <= N:
        N -= h
        rr.extend([p+offset for p in pattern])
        offset += 2

print len(rr)
print ' '.join(map(str, rr))