题目描述

有 $3^n$ 个人围在一起跳舞。他们按照顺时针分别被编号为 $0,1,2,\ldots,3^n-1$。定义一个位置的编号。

有两种舞曲。当播放第一种舞曲时，位置 $i$ 上的人会移动到位置 $j$ 上，满足将 $i,j$ 用三进制表示后，两个数对应位上的数字的和对 $3$ 取模为 $0$。当播放第二种舞曲时，位置 $i$ 上的人会移动到位置 $(i+1)\bmod 3^n$ 上。

给定一个字符串 $S$ 和 $n$，其中 $S$ 表示播放的歌单，跳舞时将按照 $S$ 的顺序播放舞曲，若 $S_i=0$ 则表示播放第一种舞曲，否则表示播放第二种舞曲。

求播放完 $S$ 后每个人所在的位置。

输入格式

第一行一个数 $n$。

第二行一个字符串 $S$，保证 $S$ 中的字符只有 $01$。

输出格式

一行 $3^n$ 个数，第 $i$ 个数表示编号 $i-1$ 的人的位置。

样例

2
101

3 2 7 0 8 4 6 5 1

第一、二、三首歌曲后每个人对应的位置为：

1 2 3 4 5 6 7 8 0
2 1 6 8 7 3 5 4 0
3 2 7 0 8 4 6 5 1

见附加文件 sample2.in

见附加文件 sample2.ans

数据范围

对于全部数据，$1\le n\le 12$，$1\le |S|\le 2\times 10^5$。