$$$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:
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.
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.
Print all the winning integers $$$x$$$ in ascending order.
3 101
4 5 6 7
1 1
2
2 01
2 3
Name |
---|