EOJ Monthly 2020.11 Sponsored by TuSimple

C. 爆炸吧现充

单点时限: 2.5 sec

内存限制: 512 MB

Little Fang 和 Cuber QQ 互相给对方准备礼物。他们各自有 $n$ 个礼物,Little Fang 的礼物的好感度为 $a_1,\ldots,a_n$,Cuber QQ 礼物的好感度为 $b_1,\ldots,b_n$。

Little Fang 选取了一个 ${1,2,\ldots,n}$ 的子集 $S$,Cuber QQ 也选了一个子集 $T$。毕竟 Little Fang 是女生,Cuber QQ 是男生,审美理解有些不同。对于 Little Fang,集合 $S$ 的礼物的总满意度是 $A(S)=\sum_{i\in S}a_i$。而对于 Cuber QQ,集合 $T$ 的礼物的总满意度是 $B(T)=\bigoplus_{i\in T}b_i$。Cuber QQ 贴心地告诉 Little Fang,$\oplus$ 是按位异或的意思。当然,对于空集,有 $A(\varnothing)=B(\varnothing)=0$。

将 Little Fang 和 Cuber QQ 的礼物放在一起,他们的幸福度都能达到 $\max(A(S),B(T))$,毕竟看见自己的礼物被对方喜爱,总还是高兴的。

Little Fang 喜欢集合并,因为两个集合的并,既有相遇,也有相离,如同她和 Cuber QQ 一同走过的路。因此她问 Cuber QQ:考虑他们选出的所有不同的 $S$ 和 $T$,且满足 $S$ 和 $T$ 的并集为 $Q$,她想知道所有情况下的幸福度的和。

Cuber QQ 由于处于热恋期,智商早没了,所以他勉强告诉了你这个问题的形式化定义:对于所有 $Q\subseteq {1,\ldots,n}$,求

$$
F(Q)=\sum_{S\cup T=Q}\max(A(S),B(T))
$$

并希望你帮他算出答案,对 $5201314$ 取模。

输入格式

第一行一个数 $n$($1\le n\le 16$)。

接下来一行 $n$ 个数表示 $a_1,\ldots,a_n$($0\le a_i< 2^7$)。

接下来一行 $n$ 个数表示 $b_1,\ldots,b_n$($0\le b_i< 2^7$ )。

输出格式

输出一行 $2^n$ 个数,设 $i$ 的二进制表示为 $(\overline{x_nx_{n-1}\ldots x_1})_2$,则第 $i$ 个数表示当 $Q= \lbrace i | x_i=1 \rbrace $ 时 $F(Q)$ 的值。

样例

Input
2
2 2
3 4
Output
0 8 10 47

提示

对于样例:

  • 当 $Q=\varnothing$ 时,$F(Q)=0$。
  • 当 $Q=\lbrace 1 \rbrace$ 时,$F(Q)=2+3+\max(2,3)=8$。
  • 当 $Q=\lbrace 2 \rbrace$ 时,$F(Q)=2+4+\max(2,4)=10$。
  • 当 $Q=\lbrace 1,2 \rbrace$ 时,考虑 $(S,T)$ 分别等于 $(\varnothing,\lbrace 1,2 \rbrace)$、$(\lbrace 1 \rbrace,\lbrace 1,2 \rbrace)$、$(\lbrace 2 \rbrace,\lbrace 1,2 \rbrace)$、$(\lbrace 1,2 \rbrace,\lbrace 1,2 \rbrace)$、$(\lbrace 2 \rbrace,\lbrace 1 \rbrace)$、$(\lbrace 1,2 \rbrace,\lbrace 1 \rbrace)$、$(\lbrace 1 \rbrace,\lbrace 2 \rbrace)$、$(\lbrace 1,2 \rbrace,\lbrace 2 \rbrace)$、$(\lbrace 1,2 \rbrace,\varnothing)$ 的情况,把满意度加起来就是 $47$。