# Subset Convolution

AC一覧

## Problem Statement (Japanese) / 問題文 (日本語)

$c_k = \sum_{i, j, i \& j = 0, i | j = k} a_i b_j$

ただし $i \& j, i | j$ はそれぞれbitwise-AND, bitwise-ORとします

## Constraints / 制約

• $0 \leq N \leq 20$
• $0 \leq a_i < 998{,}244{,}353$
• $0 \leq b_i < 998{,}244{,}353$

## Input / 入力

$N$
$a_0$ $a_1$ ... $a_{2^N - 1}$
$b_0$ $b_1$ ... $b_{2^N - 1}$


## Output / 出力

$c_0$ $c_1$ ... $c_{2^N - 1}$


## Sample / サンプル

### # 1

3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16

9 28 38 100 58 144 172 408


Timelimit: 10 secs