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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

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


n = int(input()) + 1
k = 50
while ~n >> k & 1:
	k -= 1
k -= 1
a = []
b = []
now = 1
while k >= 0:
	a = a + [now]
	b = b + [now]
	now += 1
	if n >> k & 1:
		a = a + [now]
		b = [now] + b
		now += 1
	k -= 1
print(len(a + b))
print(*a + b)


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


from collections import deque
N = int(input()) + 1
hi = 0
while 1 << hi + 1 <= N:
	hi += 1
hi -= 1
ans_A = deque()
ans_B = deque()
ptr = 1
for i in range(hi, -1, -1):
	ans_A.append(ptr)
	ans_B.append(ptr)
	ptr += 1
	if N >> i & 1:
		ans_A.append(ptr)
		ans_B.appendleft(ptr)
		ptr += 1
print(len(ans_A) * 2)
for i in range(len(ans_A)):
	print(ans_A[i], end=' ')
for i in range(len(ans_B)):
	print(ans_B[i], end=' \n'[i + 1 == len(ans_B)])


n = int(input())
a = [0]
for i in range(40):
	if n & 1 << i:
		a.append(i)
ans = []
j = 100
for i in range(len(a) - 1):
	for _ in range(a[i + 1] - a[i]):
		ans.append(j)
		j -= 1
	ans.append(i + 1)
ans = ans[:-1]
ans = [50] + [100 - i for i in range(a[-1])] + [i + 1 for i in range(len(a) - 2)][::-1] + ans + [50]
print(len(ans))
print(*ans)


n = int(input())
x = []
y = []
k = 1
for c in bin(n + 1)[2:][1:]:
	x += [k]
	y += [k]
	k += 1
	if int(c):
		x = [k] + x
		y += [k]
		k += 1
print(len(x + y))
print(*x + y)


(p, k) = ([], 1)
for i in bin(int(input()) + 1)[3:]:
	p += [k]
	k += 1
	if i == '1':
		p = [k] + p
		k += 1
p += range(1, k)
print(len(p))
print(*p)


import sys
from collections import Counter
readline = sys.stdin.readline
A = [0]
dp = [0]
N = int(readline())
cnt = 0
while N:
	cnt += 1
	idx = len(A)
	if N >= 1 + dp[-1]:
		N -= 1 + dp[-1]
		A.append(cnt)
		dp.append(1 + 2 * dp[-1])
	else:
		for l in range(len(A)):
			if N >= dp[l] + 1:
				idx = l
		N -= dp[idx] + 1
		dp = dp[:idx + 1] + [2 * dp[idx] + 1] + [dp[idx] + 1 + dp[i] for i in range(idx + 1, len(dp))]
		A = A[:idx + 1] + [cnt] + A[idx + 1:]
ans = A[1:] + list(range(1, len(A)))
print(len(ans))
print(*ans)


n = int(input())
t = n.bit_length()
n -= 2 ** (t - 1) - 1
k = t
res = list(range(1, t))
for i in range(t, -1, -1):
	if n >> i & 1:
		res.insert(i, k)
		k += 1
print(len(res) * 2)
print(' '.join(map(str, list(range(1, k)) + res)))


import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
N += 1
bit = [i for i in range(60) if N & 1 << i]
n = bit[-1]
left = deque(range(n, 0, -1))
right = deque()
x = n + 1
for i in range(n, 0, -1):
	right.append(i)
	if i - 1 in bit:
		right.append(x)
		left.appendleft(x)
		x += 1
S = list(left) + list(right)
print(len(S))
print(' '.join(map(str, S)))


n = int(input())
m = len(bin(n + 1)) - 2
n = n - (2 ** (m - 1) - 1)
fact = []
tmp = 1
for i in range(1, m + 2):
	fact.append(tmp)
	tmp = tmp * i
binom = [[0] * (m + 1) for i in range(m + 1)]
for i in range(m + 1):
	for j in range(i + 1):
		binom[i][j] = fact[i] // (fact[j] * fact[i - j])
binomsums = []
for j in range(m // 2 + 1):
	tmp = 1
	for i in range(1, j + 1):
		tmp += binom[j][i] * binom[m - j][i]
	binomsums.append(tmp)
a = [0] * (m // 2 + 1)
ind = m // 2
while n != 0:
	b = binomsums.pop()
	(c, n) = divmod(n, b)
	a[ind] = c
	ind -= 1
ans = []
i = 2
for j in range(m // 2 + 1):
	for k in range(a[j]):
		ans.append(i)
		i += 1
	ans.append(1)
ans = ans + [1 for j in range(m - m // 2 - 1)]
i -= 1
while i >= 2:
	ans.append(i)
	i -= 1
print(len(ans))
print(' '.join(map(str, ans)))


def f(n):
	if n == 1:
		return []
	if n % 2 == 0:
		r = f(n // 2)
		k = len(r)
		return r + [k + 1]
	if n % 2 == 1:
		r = f(n - 1)
		k = len(r)
		return [k + 1] + r
n = int(input())
r = f(n + 1)
k = len(r)
res = r + list(range(1, k + 1))
print(len(res))
for x in res:
	print(x, end=' ')
print()


def ncr(n, r):
	r = min(n - r, r)
	up = 1
	down = 1
	for i in range(r):
		up *= n - i
		down *= i + 1
	return up // down

def seq(x):
	s = 0
	for i in range(1, x):
		j = i * 2
		if j > x:
			break
		s += ncr(x, j)
	return s

def ins(total, p):
	s = 0
	for i in range(p + 1):
		s += ncr(p, i) * ncr(total - p, i)
	return s
ans = []
N = int(input())
k = 1
for i in range(41, 0, -1):
	x = seq(i)
	if N >= x:
		for j in range(i):
			ans.append(k)
		N -= x
		k += 1
		break
size = len(ans)
s = size // 2
while N > 90:
	m = 0
	t = 0
	for i in range(s + 1):
		tmp = ins(size, i)
		if tmp > N:
			break
		if tmp > t:
			t = tmp
			m = i
	N -= t
	ans.insert(m, k)
	ans.append(k)
	k += 1
while N > 0:
	for i in range(41, 0, -1):
		x = seq(i)
		if N >= x:
			for j in range(i):
				ans.append(k)
			N -= x
			k += 1
			break
print(len(ans))
print(' '.join([str(x) for x in ans]))


N = int(input())
n = 40
for i in range(40, -1, -1):
	if N >= (1 << i) - 1:
		n = i
		break
data = []
for i in range(n):
	data.append(i + 1)
N -= (1 << n) - 1
tmp = n
for i in range(n - 1, -1, -1):
	if N < 1 << i:
		continue
	tmp += 1
	data = data[:i] + [tmp] + data[i:]
	N -= 1 << i
ans = []
for x in range(len(data)):
	ans.append(x + 1)
ans = ans + data
print(len(ans))
print(' '.join(map(str, ans)))


def nCr(a, b):
	tmp = 1
	for i in range(a, a - b, -1):
		tmp *= i
	for i in range(1, b + 1, 1):
		tmp //= i
	return tmp
n = int(input())
out = []
co = 1
coo = 0
while n > 0:
	t = 2
	while True:
		sum1 = 0
		for j in range(2, t + 1, 2):
			sum1 += nCr(t, j)
		if n < sum1:
			t -= 1
			break
		rco = sum1
		t += 1
	ad = [co for _ in range(t)]
	sum1 = rco
	ma = sum1
	for toa in range(1, 4):
		for tob in range(1, 4):
			CO = 0
			for r in range(1, min(toa, tob) + 1):
				CO += nCr(toa, r) * nCr(tob, r)
			for a in range(1, t):
				sum2 = sum1 + (2 ** (toa + tob - 1) - 1)
				for b in range(1, a + 1):
					sum2 += nCr(a, b) * nCr(t - a, b) * CO
				if sum2 > n:
					continue
				if ma < sum2:
					ma = sum2
					ad = [co for _ in range(a)]
					for _ in range(toa):
						ad.append(100 - coo)
					for _ in range(t - a):
						ad.append(co)
					for _ in range(tob):
						ad.append(100 - coo)
	for t in ad:
		out.append(t)
	n -= ma
	coo += 1
	co += 1
print(len(out))
print(*out)


import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def f(N, i=1):
	if N == 1:
		return (deque(), deque())
	if N % 2 == 0:
		(A, B) = f(N // 2, i + 1)
		A.append(i)
		B.append(i)
		return (A, B)
	else:
		(A, B) = f(N - 1, i + 1)
		A.append(i)
		B.appendleft(i)
		return (A, B)
N = int(read()) + 1
(A, B) = f(N)
S = A + B
print(len(S))
print(*S)


def construct(N):
	for n in range(40, -1, -1):
		if N >= (1 << n) - 1:
			break
	p = []
	for i in range(1, n + 1):
		p.append(i)
	N -= (1 << n) - 1
	for i in range(n - 1, -1, -1):
		if N < 1 << i:
			continue
		n += 1
		p = p[:i] + [n] + p[i:]
		N -= 1 << i
	return p
N = int(input())
part = construct(N)
ans = part + [x + 1 for x in range(len(part))]
print(len(ans))
print(*ans, end=' ')
print()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = bin(int(input()))[2:]
	ans = [100, 100] + list(range(1, len(N))) + list(range(1, len(N)))
	k = len(N)
	for i in range(len(N) - 1):
		if N[-i - 1] == '1':
			for j in range(len(ans)):
				if ans[j] == i + 1:
					ans.insert(j, k)
					k += 1
					break
	ans += list(range(k - 1, len(N) - 1, -1))
	print(len(ans))
	print(*ans)
main()