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 PYTHON3):

Solution:
fact = [1]
for i in range(1, 101):
    fact.append(fact[-1]*i)
    
def C(a, b):
    return fact[a]//(fact[b]*fact[a-b])

def sC(a, b):
    ret = 0
    for i in range(min(b, a-b) + 1):
        ret += C(b, i) * C(a - b, i)
    return ret

def calc(n, k):
    if n<=0:
        return []
    i = 0
    while (1<<(i+1)) -1 <= n:
        i += 1
        
    ret = [str(k)] * (i+1)
    rem = n-((1<<i) - 1)
    kk = k + 1
    i += 1
    j = i // 2
    
    while j > 0:
        while True:
            tmp = sC(i, j)
            if tmp <= rem:
                ret.insert(j, str(kk))
                ret.append(str(kk))
                kk += 1
                rem -= tmp

            else:
                break
                
        j -= 1
        
    return ret + calc(rem, kk)

N = int(input())

X = calc(N, 1)
print(len(X))
print(" ".join(X))