Description

Given two sequences of length $2^n$, $a_0,a_1,\cdots,a_{2^n-1}$ and $b_0,b_1,\cdots,b_{2^n-1}$, you need to compute a sequence $c_0,c_1,\cdots,c_{2^n-1}$, where $c_k$ satisfies:

$$c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j$$

Here, $~\mid~$ denotes bitwise OR, and $\&$ denotes bitwise AND.

The answer should be taken modulo $10^9+9$.

Input Format

The first line contains a positive integer $n$, representing the size of the set.

The second line contains $2^n$ integers, describing $a$.

The third line contains $2^n$ integers, describing $b$.

Output Format

Output one line with $2^n$ integers, representing $c$.

2
1 0 2 1
2 0 2 1

2 0 6 3

Hint

For all testdata, $1\le n\le 20$, $0\le a_i,b_i< 10^9+9$.

Translated by ChatGPT 5