## Bitwise Convolution 6

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Authors:
Problem type
##### Bitwise Convolution Exercise 6

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 () and (), the exercise number and the length of the vectors and . The next line will contain and the line after will contain .

You will ouput a vector of length (not ) , the vector , where is the convolution operation of the respective subtask. Please output these numbers modulo (not ).

#### Sample Input 1

6 3
1 2 3
1 1 2

#### Sample Output 1

8 9 7 0 0 0 0 0 0

#### Explanation

We are given that . Let denote the base-3 XOR (sum of digits in base 3 without carrying) operation.

, so we add to .

, so we add to .

, so we add to .

#### Sample Input 2

6 4
1 2 2 2
1 1 2 3

#### Sample Output 2

7 7 6 5 8 10 6 0 0 0 0 0