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 $ $ \ ldots $ $ 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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

int win[1000010][20];
string S;

int winner(int x,int y){
    if(x<y){
        if(S[y-x-1]=='0') return x;
        else return y;
    }else{
        if(S[x-y-1]=='0') return y;
        else return x;
    }
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin>>N;
  cin>>S;
  int M=pow(2,N);
  vector<int> P(M);
  rep(i,M) cin>>P[i];

  vector<int> A(2*M);
  rep(i,2*M) A[i]=P[i%M];

  for(int i=0;i<2*M;i++) win[i][0]=A[i];

  for(int k=1;k<=N;k++){
      for(int j=0;j+k-1<2*M;j++){
          int rig=j+(1<<(k-1));
          win[j][k]=winner(win[j][k-1],win[rig][k-1]);
      }
  }

  for(int i=0;i<M;i++) cout<<win[i][N]<<"\n";

  return 0;
}

