京都大学クスノキ前にて、$2$ 人用対戦ゲームのトーナメントが行われようとしています。
このトーナメントの参加者は $2^N$ 人いて、 $1$ から $2^N$ までの番号がついています。
参加者のうちの $2$ 人が戦った時の勝敗は、$0$ と $1$ からなる長さ $2^N-1$ の文字列 $S$ によって表されます。
人 $x$ と人 $y$ $(1 \le x < y \le 2^N)$ が戦ったとき、
ことが分かっています。
トーナメントは参加者が一列に並ぶことで始まり、以下の通りに進行します。
いま、参加者は初期状態として、先頭から $i$ 番目 $(1 \le i \le 2^N)$ が人 $P_i$ となるように並んでいます。
$0 \le k \le 2^N-1$ を満たすすべての整数 $k$ について、以下の問題を解いてください。
入力は以下の形式で標準入力から与えられる。
$N$
$S_1S_2 \ldots S_{2^N-1}$
$P_1$ $P_2$ $\ldots$ $P_{2^N}$
$2^N$ 行出力せよ。
$i$ 行目 $(1 \le i \le 2^N)$ には、$k = i-1$ としたときの上記の問題の答えを出力せよ。
2 100 1 4 2 3
1 2 1 2
例えば $k = 2$ としたとき、移動後の列における参加者の番号を先頭から挙げていくと、 $2, 3, 1, 4$ となります。
人 $2$ と 人 $3$ が戦うと、 $S_1 = 1$ より人 $3$ が勝ちます。
人 $1$ と 人 $4$ が戦うと、 $S_3 = 0$ より人 $1$ が勝ちます。
人 $3$ と 人 $1$ が戦うと、 $S_2 = 0$ より人 $1$ が勝ちます。
したがって、 $k = 2$ の場合の優勝者は、人 $1$ となります。
4 101011100101000 8 15 2 9 12 5 1 7 14 10 11 3 4 6 16 13
16 1 16 2 16 12 10 14 16 1 16 2 16 12 10 14
1 0 1 2
1 1