Playoff
Contest: Educational Codeforces Round 140 (Rated for Div. 2)
Difficulty rating: 1500
Tags: combinatorics, constructive algorithms, dp, greedy, math

$$$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 format:
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 format:
Print all the winning integers $$$x$$$ in ascending order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
101

Example output:
4 5 6 7

Example input:
1
1

Example output:
2

Editorial:
Firstly, let's prove that the order of characters in $$$s$$$ is interchangeable.
Suppose we have a tournament of four teams with skills $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ such that $$$a < b < c < d$$$; and this tournament has the form $$$01$$$ or $$$10$$$. It's easy to see that $$$a$$$ and $$$d$$$ cannot be winners, since $$$a$$$ will be eliminated in the round with type $$$1$$$, and $$$d$$$ will be eliminated in the round with type $$$0$$$. However, it's easy to show that both with $$$s = 10$$$ and with $$$s = 01$$$, $$$b$$$ and $$$c$$$ can be winners.
Using this argument to matches that go during phases $$$i$$$ and $$$i+1$$$ (a group of two matches during phase $$$i$$$ and a match during phase $$$i + 1$$$ between the winners of those matches can be considered a tournament with $$$n = 2$$$), we can show that swapping $$$s_i$$$ and $$$s_{i+1}$$$ does not affect the possible winners of the tournament.
So, suppose all phases of type $$$1$$$ happen before phases of type $$$0$$$, there are $$$x$$$ phases of type $$$1$$$ and $$$y$$$ phases of type $$$0$$$ ($$$x + y = n$$$). $$$2^{x+y} - 2^y$$$ teams will be eliminated in the first part (phases of type $$$1$$$), and the team with the lowest skill that wasn't eliminated in the first half will win the second half.
It's easy to see that the teams with skills $$$[1..2^x-1]$$$ cannot pass through the first part of the tournament, since to pass the first part, a team has to be the strongest in its "subtree" of size $$$2^x$$$.
Furthermore, since the minimum of $$$2^y$$$ teams passing through the first half wins, the winner should have skill not greater than $$$2^{x+y}-2^y+1$$$ — the winner should have lower skill than at least $$$2^y - 1$$$ teams, so teams with skills higher than $$$2^{x+y}-2^y+1$$$ cannot win.
Okay, now all possible winners belong to the segment $$$[2^x, 2^n - 2^y + 1]$$$. Let's show that any integer from this segment can be winning.
Suppose $$$k \in [2^x, 2^n - 2^y + 1]$$$, let's construct the tournament in such a way that only team with skill $$$k$$$ and $$$2^y-1$$$ teams with the highest skill pass through the first part of the tournament (obviously, then team $$$k$$$ wins). There are $$$2^y$$$ independent tournaments of size $$$2^x$$$ in the first part; let's assign teams with skills from $$$1$$$ to $$$2^x-1$$$, and also the team $$$k$$$ to one of those tournaments; for all other $$$2^y-1$$$ tournaments, let's assign the teams in such a way that exactly one team from the $$$2^y-1$$$ highest ones competes in each of them. It's easy to see that the team $$$k$$$ will win its tournament, and every team from the $$$2^y-1$$$ highest ones will win its tournament as well, so the second half will contain only teams with skills $$$k$$$ and $$$[2^n-2^y+2..2^n]$$$ (and, obviously, $$$k$$$ will be the winner of this tournament).
So, the answer to the problem is the segment of integers $$$[2^x, 2^n - 2^y + 1]$$$.