【模板】子集卷积

题目背景

这是一道模板题。

题目描述

给定两个长度为 $2^n$ 的序列 $a_0,a_1,\cdots,a_{2^n-1}$ 和 $b_0,b_1,\cdots,b_{2^n-1}$,你需要求出一个序列 $c_0,c_1,\cdots,c_{2^n-1}$,其中 $c_k$ 满足: $$c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j$$ 其中$~\mid~$表示按位或,$\&$表示按位与。 答案对 $10^9+9$ 取模。

输入输出格式

输入格式


第一行输入一个正整数 $n$ ,表示集合的大小。 第二行有 $2^n$ 个整数,描述了 $a$。 第三行有 $2^n$ 个整数,描述了 $b$。

输出格式


输出一行 $2^n$ 个整数,表示 $c$。

输入输出样例

输入样例 #1

2
1 0 2 1
2 0 2 1

输出样例 #1

2 0 6 3

说明

对于所有数据,$1\le n\le 20$,$0\le a_i,b_i< 10^9+9$。 可能轻微卡常,请注意读入效率。