p03769 AtCoder Grand Contest 012 - Tautonym Puzzle
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
```python
def test():
    from itertools import combinations

    s = '111223111223'
    result = 0
    for k in range(1, len(s) // 2 + 1):
        for idx in combinations(range(len(s)), 2 * k):
            success = True
            for ii in range(k):
                if s[idx[ii]] != s[idx[ii + k]]:
                    success = False
                    break
            if success:
                result += 1
    print(result)


n = int(input())

factorials = [1, 1]
for i in range(2, 40):
    factorials.append(factorials[-1] * i)

patterns = {}
for i in range(2, 40):
    base = (1 << (i - 1)) - 1
    gain = base
    chars = i
    if gain > n:
        break
    if gain not in patterns or chars < patterns[gain][0]:
        patterns[gain] = (chars, (i,))
    if i % 2 == 1:
        continue

    a = i // 2
    ncr1 = factorials[i] // factorials[a] // factorials[a] - 1

    for b in range(1, a + 1):
        base2 = (1 << (2 * b - 1)) - 1
        ncr2 = factorials[2 * b] // factorials[b] // factorials[b] - 1
        gain = base + base2 + ncr1 * ncr2
        chars = i + 2 * b
        if gain > n:
            break
        if gain not in patterns or chars < patterns[gain][0]:
            patterns[gain] = (chars, (a, b))

        for c in range(1, b + 1):
            base3 = (1 << (2 * c - 1)) - 1
            ncr3 = factorials[2 * c] // factorials[c] // factorials[c] - 1
            gain = base + base2 + base3 + ncr1 * ncr2 * ncr3 + ncr1 * ncr2 + ncr2 * ncr3 + ncr3 * ncr1
            chars = i + 2 * b + 2 * c
            if gain > n:
                break
            if gain not in patterns or chars < patterns[gain][0]:
                patterns[gain] = (chars, (a, b, c))

            for d in range(1, c + 1):
                base4 = (1 << (2 * d - 1)) - 1
                ncr4 = factorials[2 * d] // factorials[d] // factorials[d] - 1
                gain = base + base2 + base3 + base4 + ncr1 * ncr2 * ncr3 * ncr4
                gain += ncr1 * ncr2 * ncr3 + ncr1 * ncr2 * ncr4 + ncr1 * ncr3 * ncr4 + ncr2 * ncr3 * ncr4
                gain += ncr1 * ncr2 + ncr1 * ncr3 + ncr1 * ncr4 + ncr2 * ncr3 + ncr2 * ncr4 + ncr3 * ncr4
                chars = i + 2 * b + 2 * c + 2 * d
                if gain > n:
                    break
                if gain not in patterns or chars < patterns[gain][0]:
                    patterns[gain] = (chars, (a, b, c, d))


def dfs(use, i, remaining, total_char):
    if remaining == 0:
        return total_char <= 200

    for j in range(i, len(patterns)):
        gain, (chars, lengths) = patterns[j]
        if total_char + remaining * chars / gain > 200:
            break
        if gain > remaining:
            continue
        use.append(lengths)
        result = dfs(use, j, remaining - gain, total_char + chars)
        if result:
            return True
        use.pop()

    return False


patterns = sorted(patterns.items(), key=lambda item: item[0] / item[1][0], reverse=True)

use = []
result = dfs(use, 0, n, 0)
assert result

ans = []
c = 1
for lengths in use:
    if len(lengths) == 1:
        ans.extend([c] * lengths[0])
        c += 1
    else:
        for _ in range(2):
            for i, l in enumerate(lengths):
                ans.extend([c + i] * l)
        c += len(lengths)

print(len(ans))
print(*ans)

```