题目描述

这是一道模板题。

给出两个集合幂级数 $f,g$，求它们的不相交集合并卷积。

卷积在模 $10^9 + 9$ 意义下进行。

输入格式

第一行输入一个数 $n$，表示集合的大小。

第二行有 $2^n$ 个数，描述了 $f$。

第三行有 $2^n$ 个数，描述了 $g$。

输出格式

输出一行 $2^n$ 个数，表示 $f$ 和 $g$ 卷积后的结果。

样例

input

2
1 0 2 1
2 0 2 1

output

2 0 6 3

数据范围与提示

对于所有数据，$1 \leq n \leq 20, 0 \leq f_i, g_i < 10^9 + 9$。