暂无测试数据。

从前有个熊孩子，他有一个数组 $a$，下标从 $0$ 到 $2^n-1$，他还会一种位运算 $cal(i,j)$，其中 $i$ 和 $j$ 都是布尔型的变量。现在他想生成一个数组 $b$，规则如下：

对于任意的一对 $i, j(0\le i,j< 2^n)$，熊孩子由 $i$ 和 $j$ 得到一个数 $k$，对于 $k$ 的二进制前 $n$ 位，第 $x$ 位等于 $cal(i$的第 $x$ 位, $j$ 的第 $x$ 位$)$，$k$ 的比第 $n$ 位还高的二进制位等于 $0$。如果 $k$ 等于 $i$，那么令 $b[i]+=a[j]$，每一对只计算一次。

在给你数组 $a$ 和位运算的真值表，请你求出数组 $b$。

输入格式

第一行一个整数 $N$，数值上等于 $2^n$，代表数组长度。

接下来 $N$ 个整数，代表数组 $a$。

接下来一个 $2*2$ 的矩阵，代表位运算的真值表。行代表运算的第一个数，第一行代表 $0$，第二行代表 $1$。列代表运算的第二个数，第一列代表 $0$，第二列代表 $1$。

输出格式

一行 $N$ 个数，代表数组 $b$。

数据规模

对于 $30\%$ 的数据：$N \le 1024$。

对于另外 $10\%$ 的数据：真值表为

0 1
1 0

对于另外10%的数据：真值表为

1 0
1 0

对于 $100\%$ 的数据：$N \le 131072$，$a[i] \le 1000$。

样例解释

$b_0 = a_0 + a_1 + a_2 + a_3 = 10$。

$b_1 = a_1 + a_3 = 6$。

$b_2 = a_2 + a_3 = 7$。

$b_3 = a_3 = 4$

4
1 2 3 4
0 0
0 1

10 6 7 4