$2^n$ teams participate in a playoff tournament. The tournament consists of $2^n - 1$ games. They are held as follows: in the first phase of the tournament, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$, and so on (so, $2^{n-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{n-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, the second phase begins, where $2^{n-2}$ games are played: in the first one of them, the winner of the game "$1$ vs $2$" plays against the winner of the game "$3$ vs $4$", then the winner of the game "$5$ vs $6$" plays against the winner of the game "$7$ vs $8$", and so on. This process repeats until only one team remains.

The skill level of the $i$-th team is $p_i$, where $p$ is a permutation of integers $1$, $2$, ..., $2^n$ (a permutation is an array where each element from $1$ to $2^n$ occurs exactly once).

You are given a string $s$ which consists of $n$ characters. These characters denote the results of games in each phase of the tournament as follows:

if $s_i$ is equal to 0, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the lower skill level wins;

if $s_i$ is equal to 1, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the higher skill level wins.

Let's say that an integer $x$ is winning if it is possible to find a permutation $p$ such that the team with skill $x$ wins the tournament. Find all winning integers.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 18$).

The second line contains the string $s$ of length $n$ consisting of the characters 0 and/or 1.


-----Output-----

Print all the winning integers $x$ in ascending order.


-----Examples-----

Input
3
101
Output
4 5 6 7
Input
1
1
Output
2
Input
2
01
Output
2 3


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM
Tags: Constructive algorithms

Combinatorics

Greedy algorithms

Dynamic programming

Mathematics


Solutions:
import sys
import re
import math
from math import log2
from math import log
from math import ceil
from math import gcd
from decimal import *
from datetime import date
from collections import deque
import random
import heapq
import itertools
import datetime
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
line = input()
cannot = {}
(small, big) = (1, 2 ** n)
(smallt, bigt) = (1, 1)
for term in line:
	if term == '1':
		small += smallt
		smallt *= 2
	else:
		big -= bigt
		bigt *= 2
ans = [str(i) for i in range(small, big + 1)]
print(' '.join(ans))


import os
import math
import collections
import bisect
import functools
import itertools
import heapq
import sys

def solve(a, n):
	(c0, c1) = (a.count(0), a.count(1))
	m = 1 << n
	if c0 == 0:
		return [m]
	if c1 == 0:
		return [1]
	(l, r) = (2 ** c1, 2 ** c0)
	ans = [i for i in range(1, m + 1) if l <= i <= m - r + 1]
	return ans
n = int(input())
a = [int(c) for c in input()]
res = solve(a, n)
print(' '.join(map(str, res)))


k = int(input())
max = 2 ** k
s = str(input())
arr = [int(x) for x in s]
sum = 0
for i in arr:
	sum += i
start = 2 ** sum
end = max - 2 ** (k - sum) + 1
m = start
ans = []
while m <= end:
	ans.append(m)
	m += 1
result = ' '.join((str(item) for item in ans))
print(result)


I = input
n = int(input())
x = I()
print(*range(2 ** x.count('1'), 2 ** n - 2 ** x.count('0') + 2))


n = int(input())
s = input().count('1')
print(*range(2 ** s, 2 ** n - 2 ** (n - s) + 2))


n = int(input())
s = input()
arr = list(range(1, 2 ** n + 1))
l = 0
r = len(arr) - 1
r_change = 1
l_change = 1
for i in range(len(s)):
	if s[i] == '0':
		r -= r_change
		r_change *= 2
	else:
		l += l_change
		l_change *= 2
print(*arr[l:r + 1])


n = int(input())
s = input()
z = s.count('0')
o = n - z
res = list(range(pow(2, o), pow(2, n) + 2 - pow(2, z)))
print(*res)


n = int(input())
s = input()
m = 2 ** n
fir = 2 ** s.count('1')
sec = 2 ** s.count('0')
print(*[x for x in range(fir, m - sec + 2)])


import sys
input = sys.stdin.readline
inp = sys.stdin.readline

def input():
	return inp().strip()

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def solve():
	n = ii()
	m = input()
	arr = [i for i in range((1 << n) + 1)]
	l = 1
	r = 1
	for i in m:
		if i == '0':
			r <<= 1
		else:
			l <<= 1
	print(*arr[l:len(arr) - r + 1])

def main():
	solve()
main()


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	s = readStr()
	cnt = 0
	for i in range(n):
		cnt += int(s[i])
	ans = [i for i in range(pow(2, cnt), pow(2, n) - (pow(2, n - cnt) - 1) + 1)]
	return ans
print(*solve())


n = int(input())
st = input()
s = 0
for i in range(n):
	if st[i] == '1':
		s += 1
l = 2 ** s
r = 2 ** n - 2 ** (n - s) + 2
out = ''
for i in range(l, r):
	out += str(i) + ' '
print(out)


n = int(input())
s = input()
import collections
can = collections.deque(range(1, 2 ** n + 1))
l = 0
r = 0
for i in range(n):
	if s[i] == '0':
		for _ in range(2 ** r):
			can.pop()
		r += 1
	else:
		for _ in range(2 ** l):
			can.popleft()
		l += 1
print(*can)


roll = int(input())
bin = input()
bin = bin[::-1]
working = []
if bin[0] == '1':
	working = [2, 2]
else:
	working = [1, 1]
for i in range(1, len(bin)):
	if bin[i] == '1':
		working = [2 * working[0], 2 ** i + working[1]]
	else:
		working = [working[0], 2 * working[1] - 1]
blank = ''
for i in range(working[0], working[1]):
	blank += str(i) + ' '
blank += str(working[1])
print(blank)


n = int(input())
s = list(input())
ones = 0
zeros = 0
for ss in s:
	if ss == '1':
		ones += 1
	else:
		zeros += 1
out = ''
for i in range(2 ** ones, 2 ** n + 2 - 2 ** zeros):
	out += str(i) + ' '
print(out[:-1])


n = int(input())
s = input()
a = list(map(int, s))
x = a.count(1)
y = a.count(0)
ans = [i for i in range(2 ** x, 2 ** n - 2 ** y + 2)]
print(*ans)


n = int(input())
s = input()
count1 = s.count('1')
count0 = s.count('0')
for i in range(2 ** count1, 2 ** n - 2 ** count0 + 2):
	print(i, end=' ')


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	s = inp_str()
	cnt = [0, 0]
	for i in range(n):
		cnt[int(s[i])] += 1
	left = 1 + (2 ** cnt[1] - 1)
	right = 2 ** n - (2 ** cnt[0] - 1)
	for i in range(left, right + 1):
		print(i, end=' ')
	print('')
tt = 1
for t in range(tt):
	solve()


n = int(input())
s = input()
one = 0
zer = 0
for j in s:
	if j == '0':
		zer += 1
	else:
		one += 1
ans = []
for j in range(2 ** one, 2 ** n - 2 ** zer + 2):
	ans.append(j)
print(*ans)


n = int(input())
s = input()
z = 0
o = 0
for i in s:
	if i == '1':
		o += 1
	else:
		z += 1
for i in range(2 ** o, 2 ** n - 2 ** z + 1 + 1):
	print(i, end=' ')


t = int(input())
a = input()
w = a.count('1')
y = len(a) - w
for i in range(2 ** w, 2 ** t - 2 ** y + 2):
	print(i, end=' ')


power = 2 ** int(input())
result = input()
lower = 2 ** result.count('1')
upper = power - 2 ** result.count('0') + 1
ans = []
for i in range(lower, upper + 1):
	ans.append(i)
print(*ans)


import math
t = 1
for _ in range(t):
	n = int(input())
	s = input()
	(l, h) = (1, 2 ** n)
	i = 0
	j = 0
	for ele in s:
		if ele == '1':
			l += 2 ** i
			i += 1
		else:
			h -= 2 ** j
			j += 1
	for x in range(l, h + 1):
		print(x, end=' ')


import sys
n = int(input())
s = input()
(a, b) = (0, 0)
(x, y) = (1, 2 ** n)
for i in range(n):
	if s[i] == '0':
		y -= 2 ** b
		b += 1
	else:
		x += 2 ** a
		a += 1
ans = []
for j in range(x, y + 1):
	ans.append(j)
print(*ans)


n = int(input())
string = input()
count = 0
for i in range(n):
	if string[i] == '1':
		count += 1
start = 2 ** count
end = 2 ** n - 2 ** (n - count) + 1
for i in range(start, end + 1):
	print(i, end=' ')
print()


n = int(input())
s = input()
init = 2 ** s.count('1')
total = 2 ** n
fin = total - 2 ** s.count('0')
arr = []
for i in range(init, fin + 2):
	arr.append(i)
print(*arr)


import math
import collections
for _ in range(1):
	n = int(input())
	s = input()
	i = 1
	j = 2 ** n
	left = 1
	right = 1
	for k in s:
		if k == '1':
			i += left
			left *= 2
		else:
			j -= right
			right *= 2
	l = []
	for j in range(i, j + 1):
		l.append(j)
	print(*l)


n = int(input())
a = input()
k = a.count('1')
t = pow(2, n)
if k == 0:
	print(1)
elif k == n:
	print(t)
else:
	m1 = pow(2, k)
	min = 1
	oraliq = 1
	max = t
	for x in a:
		if x == '1':
			min += oraliq * t // 2
		else:
			max -= oraliq
			oraliq *= 2
		t //= 2
	for x in range(m1, max + 1):
		print(x, end=' ')
	print()


n = int(input())
s = str(input())
a1 = s.count('1')
a0 = n - a1
b1 = pow(2, a1)
b0 = pow(2, a0)
c = pow(2, n) - b0 + 2
for i in range(b1, c):
	print(i, end=' ')


n = int(input())
s = input()
l = 0
r = 0
for i in range(len(s)):
	if s[i] == '1':
		l = l * 2 + 1
	else:
		r = r * 2 + 1
r = pow(2, n) - r
for i in range(l + 1, r + 1):
	print(i, end=' ')


n = int(input())
s = input()
for i in range(pow(2, s.count('1')), pow(2, n) - pow(2, s.count('0')) + 2):
	print(i, end=' ')
print()


n = int(input())
s = input()
nz = 0
for j in range(0, n):
	if s[j] == '0':
		nz = nz + 1
n1 = n - nz
x = pow(2, n1)
y = pow(2, n) - pow(2, nz) + 1
for j in range(x, y + 1):
	print(j, end=' ')
print('')


n = int(input())
s = input()
lo = 1
hi = 2 ** n
count0 = 1
count1 = 1
for x in s:
	if x == '0':
		hi -= count0
		count0 <<= 1
	else:
		lo += count1
		count1 <<= 1
for i in range(lo, hi + 1):
	print(i, end=' ')
print()


import math
from collections import Counter

def li():
	return list(map(int, input().split()))

def nt():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L
size = nt()
s = input()
z = s.count('0')
o = size - z
l = 1 << o
u = (1 << size) - (1 << z) + 1
L = [i for i in range(l, u + 1)]
print(*L)


n = int(input())
string = input()
c0 = 0
c1 = 0
for i in range(n):
	if string[i] == '0':
		c0 += 1
	else:
		c1 += 1
a = 2 ** c1 - 1
b = 2 ** n - (2 ** c0 - 1)
for j in range(a + 1, b + 1):
	print(j, end=' ')
print('')


n = int(input())
s = input()
a = s.count('1')
b = s.count('0')
l = []
for i in range(2 ** a, 2 ** n - (2 ** b - 2)):
	print(i, end=' ')


n = int(input())
s = input()
start = 1
end = 2 ** n
ones = s.count('1')
zeros = s.count('0')
start += 2 ** ones - 1
end -= 2 ** zeros - 1
for val in range(start, end + 1):
	print(val, end=' ')
print()


n = int(input())
s = input()
one = s.count('1')
zero = s.count('0')
for j in range(2 ** one, 2 ** n - 2 ** zero + 2):
	print(j, end=' ')


n = int(input())
L = list(input())
c = L.count('1')
c2 = L.count('0')
for j in range(2 ** c, 2 ** n - 2 ** c2 + 2):
	print(j, end=' ')


n = int(input())
ss = input()
sum1 = 0
sum0 = 0
for i in ss:
	if i == '0':
		sum0 += 1
	if i == '1':
		sum1 += 1
for i in range(2 ** sum1, 2 ** n - 2 ** sum0 + 2):
	print(i, end=' ')


n = int(input())
s = input()
larger = 0
smaller = 0
for i in range(len(s)):
	if s[i] == '1':
		smaller += 1
	else:
		larger += 1
for i in range(2 ** smaller, 2 ** n - (2 ** larger - 2)):
	print(i, end=' ')


n = int(input())
s = list(input())
mn = 2 ** s.count('1')
mx = 2 ** n - 2 ** s.count('0') + 1
for i in range(mn, mx + 1):
	print(i, end=' ')


n = int(input())
t = 2 ** n
s = input()
cnt = 0
for i in range(len(s)):
	cnt += int(s[i])
if cnt == 0:
	print(1)
else:
	left = 2 ** cnt
	ans = []
	for i in range(1, t + 1):
		if i < left:
			continue
		sm = i - left
		bg = t - left - sm
		rem = cnt
		while rem > 0:
			if bg >= sm:
				sm = 0
				break
			sm -= bg
			sm //= 2
			rem -= 1
		if sm == 0:
			ans.append(str(i))
	print(' '.join(ans))


n = int(input())
s = input()
ones = s.count('1')
zeros = s.count('0')
a = 2 ** ones
b = 2 ** n - 2 ** zeros + 1
for i in range(a, b + 1):
	print(i, end=' ')


n = int(input())
s = input()
k = s.count('1')
if k == n:
	print(pow(2, n))
	exit(0)
kk = s.count('0')
be = 1 << k
f = [0] * 22
f[0] = 1
for i in range(1, 22):
	f[i] = f[i - 1] * 2
for i in range(1, n):
	f[i] = f[i - 1] + f[i]
en = pow(2, n) - f[kk - 1]
for i in range(be, en + 1):
	print(i, end=' ')


import math
n = int(input())
s = input()
a = s.count('1')
b = s.count('0')
m = pow(2, n)
aa = pow(2, a) - 1
bb = pow(2, b) - 1
for i in range(aa + 1, m - bb + 1):
	print(i, end=' ')


t = int(input())
arr = input()
i = 1
j = 1
r = 1
l = 1
for y in range(t):
	r *= 2
for x in arr:
	if x == '1':
		l += i
		i *= 2
	if x == '0':
		r -= j
		j *= 2
for x in range(l, r + 1):
	print(x, end=' ')


n = int(input())
s = input()
l = [s.count('0'), s.count('1')]
zeros = l[0]
ones = l[1]
start = 2 ** ones
ending = 2 ** n - 2 ** zeros + 1
for i in range(start, ending + 1):
	print(i, end=' ')


n = int(input())
l = 1
r = int(2 ** n)
s = input()
nl = 0
nr = 0
for ch in s:
	if ch == '0':
		r = r - int(2 ** nr)
		nr += 1
	else:
		l = l + int(2 ** nl)
		nl += 1
for i in range(l, r + 1):
	if i != r:
		print(i, end=' ')
	else:
		print(i)


t = int(input())
st = input()
n0 = 0
n1 = 0
j = 0
while 0 <= j < t:
	if int(st[j]) == 0:
		n0 = n0 + 1
	elif st[j] == '1':
		n1 = n1 + 1
	j = j + 1
y1 = pow(2, t) - pow(2, n0) + 1
x1 = pow(2, n1)
j = x1
while x1 <= j <= y1:
	print(j, end=' ')
	j = j + 1
print('')


n = int(input())
s = input()
(one, zero) = (0, 0)
for i in s:
	if i == '0':
		zero += 1
	else:
		one += 1
for i in range(2 ** one, 2 ** n - 2 ** zero + 2):
	print(i, end=' ')
print()


n = int(input())
rates = input()
num_1 = 0
num_0 = 0
for i in range(n):
	if rates[i] == '1':
		num_1 += 1
	else:
		num_0 += 1
for i in range(2 ** num_1, 2 ** n - 2 ** num_0 + 2):
	print(i, end=' ')


import os, sys
if os.getlogin() == 'Arun-Rog':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
from collections import defaultdict
a = int(input())
st = input()
d = defaultdict(lambda : 0)
for x in st:
	d[x] += 1
k = 2 ** d['1'] - 1
m = 2 ** d['0'] - 1
for i in range(k, 2 ** a - m):
	print(i + 1, end=' ')


from collections import Counter
n = int(input())
nums = list(input())
s = Counter(nums)
ones = 2 ** s['1'] - 1
zeros = 2 ** s['0'] - 1
max = 2 ** n
for i in range(max + 1):
	if ones < i <= max - zeros:
		print(i, end=' ')
	if i >= max - zeros:
		break


J = input
I = range
G = 1
for K in I(G):
	B = int(J())
	H = J()
	L = []
	C = 0
	D = 0
	E = 1
	F = 2 ** B
	for A in H:
		if A == '0':
			F -= 2 ** D
			D += 1
		else:
			E += 2 ** C
			C += 1
	for A in I(E, F + 1):
		if A > 2 ** B:
			continue
		print(A, end=' ')


n = int(input())
s = input()
ans = []
zer = s.count('0')
one = s.count('1')
c = 2 ** one
d = 2 ** zer - 1
for i in range(1, 2 ** n + 1):
	if i >= c and i <= 2 ** n - d:
		ans.append(i)
for j in ans:
	print(j, end=' ')


n = int(input())
s = input()
zs = s.count('0')
os = s.count('1')
[print(i, end=' ') for i in range(1, 2 ** n + 1) if 2 ** os - 1 < i <= 2 ** n - (2 ** zs - 1)]