Bitwise Convolution Exercise 4, 5

This is a practice problem for bitwise convolution using the Fast Walsh–Hadamard transform. Exercises come from here.

1. Exercise 1: Bitwise XOR convolution

2. Exercise 2: Bitwise OR convolution

3. Exercise 3: Bitwise AND convolution

4. Exercise 4: An operation that ORs the first bit, ANDs the second bit, and then repeats.

5. Exercise 5: An operation that ORs the first bit, ANDs the second bit, XORs the third one, and then repeats.

6. Exercise 6: XOR in base 3 (addition with no carry).

Input and Output Specification

The first line contains the integers ~K~ (~4\leq K \leq 5~) and ~N~ (~N \leq 2\cdot 10^5~), the exercise number and the length of the vectors ~A~ and ~B~. The next line will contain ~A~ and the line after will contain ~B~.

You will ouput a vector of length ~2N~, the vector ~C = A$B~, where ~$~ is the convolution operation of the respective subtask. Please output these numbers modulo ~10^9+9~.

Sample Input 1

4 4
1 2 1 2
1 2 3 4

Sample Output 1

5 34 3 18 0 0 0 0

Explanation

We are given that ~K = 4, N = 4, A = \{1, 2, 1, 2\}, B = \{1, 2, 3, 4\}~. Let ~$~ denote the convolution operation.

~0$0 = 0~, so add ~a_0\cdot b_0 = 1\cdot 1~ to ~c_0~.

~0$1 = 1~, so add ~a_0\cdot b_1 + a_1\cdot b_0 = 1\cdot 2 + 2\cdot 1~ to ~c_1~.

~0$2 = 0~, so add ~a_0\cdot b_2 + a_2\cdot b_0 = 1\cdot 3 + 1\cdot 1~ to ~c_0~.

~0$3 = 1~, so add ~a_0\cdot b_3 + a_3\cdot b_0 = 1\cdot 4 + 2\cdot 1~ to ~c_1~.

~\ldots~

We already see from above that ~c_0 = 5~