Problem statement

A $ 2 $ human-player match-up game tournament is about to take place in front of Kyoto University Camphor Tree.

There are $ 2 ^ N $ participants in this tournament, numbered from $ 1 $ to $ 2 ^ N $.

Winning or losing when $ 2 $ of participants fight is represented by the $ 2 ^ N-1 $ string $ S $ consisting of $ 0 $ and $ 1 $.

When people $ x $ and people $ y $$ (1 \ le x <y \ le 2 ^ N) $ fight

• When $ S_ {y-x} = 0 $, the person $ x $ wins,
• When $ S_ {y-x} = 1 $, the person $ y $ wins

I know that.

The tournament begins with a line of participants and proceeds as follows:

1. Make a pair of $ 2 $ people from the beginning of the column. For every pair, $ 2 $ people in the pair fight.
2. Those who win the match in 1 will remain in the line, and those who lose will leave the line.
3. If there are more than $ 2 $ left, fill the column back to 1.
4. If there are $ 1 $ left, that person will be the winner.

Now, the participants are initially arranged so that the $ i $ th $(1 \ le i \ le 2 ^ N)$ from the beginning becomes the person $ P_i $.

Solve the following problem for all integers $ k $ that satisfy $0 \ le k \ le 2 ^ N-1$.

• From the initial state, the first $ k $ person moves to the end of the column without changing the order.
• In other words, if you list the number of participants in the moved column from the beginning, $ P_ {k + 1}, P_ {k + 2}, ..., P_ {2 ^ N}, P_1, P_2, ..., P_k $.
• Find the winner's number when you start the tournament from the line after the move.

Constraint

• $1 \ leq N \ leq 18$
• $ N $ is an integer.
• $ S $ is a $ 2 ^ N-1 $ string consisting of $ 0 $ and $ 1 $.
• $ P $ is a permutation of integers from $ 1 $ to $ 2 ^ N $.

input

Input is given from standard input in the following format.

$ N $
$S_1S_2 \ ldots S_ {2 ^ N-1}$
$ P_1 $ $ P_2 $ $\$ $ P_ {2 ^ N} $

output

Output $ 2 ^ N $ lines.

In the $ i $ line $(1 \ le i \ le 2 ^ N)$, output the answer to the above problem when $ k = i-1 $.

Input example 1

2
100
1 4 2 3

Output example 1

1
2
1
2

For example, if $ k = 2 $, the number of participants in the moved column will be $ 2, 3, 1, 4 $ from the beginning.

When person $ 2 $ and person $ 3 $ fight, person $ 3 $ wins over $ S_1 = 1 $.

When person $ 1 $ and person $ 4 $ fight, person $ 1 $ wins over $ S_3 = 0 $.

When person $ 3 $ and person $ 1 $ fight, person $ 1 $ wins over $ S_2 = 0 $.

Therefore, if $ k = 2 $, the winner would be $ 1 $ person.

Input example 2

Four
101011100101000
8 15 2 9 12 5 1 7 14 10 11 3 4 6 16 13

Output example 2

16
1
16
2
16
12
Ten
14
16
1
16
2
16
12
Ten
14

Input example 3

1
0
1 2

Output example 3

1
1

Example

Input

2
100
1 4 2 3

Output

1
2
1
2

见题面

见题面