Bitwise OR and AND Convolution

You are given two sequences a₀, a₁, \(\ldots\), a_2^n-1 and b₀, b₁, \(\ldots\), b_2^n-1 of length \(2^n\). Your task is to compute a new sequence c₀, c₁, \(\ldots\), c_2^n-1 such that for every \(0 \le k < 2^n\),

[ c_k = \sum_{\substack{i & j = 0 \ i \mid j = k}} a_i \cdot b_j \mod (10^9+9), ]

where \(i \& j = 0\) means the bitwise AND of \(i\) and \(j\) is zero and \(i \mid j = k\) means the bitwise OR of \(i\) and \(j\) equals \(k\). All arithmetic is performed modulo \(10^9+9\).

inputFormat

The first line contains an integer \(n\). The second line contains \(2^n\) integers representing the sequence \(a_0, a_1, \ldots, a_{2^n-1}\). The third line contains \(2^n\) integers representing the sequence \(b_0, b_1, \ldots, b_{2^n-1}\).

outputFormat

Output a single line containing \(2^n\) integers: \(c_0, c_1, \ldots, c_{2^n-1}\), separated by spaces. Each \(c_k\) is computed modulo \(10^9+9\).

sample

1
1 2
3 4

3 10