#152. 子集卷积

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Dance_Of_Faith

题目描述

这是一道模板题。

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

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

输入格式

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

第二行有 2^n 个数,描述了 f

第三行有 2^n 个数,描述了 g

输出格式

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

样例

样例输入

2
1 0 2 1
2 0 2 1

样例输出

2 0 6 3

数据范围与提示

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