单点时限: 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)$ 的值。
2 2 2 3 4
0 8 10 47
对于样例：