## Bitwise Convolution 4, 5

##### Bitwise Convolution Exercise 4, 5

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

Exercise 1: Bitwise XOR convolution

Exercise 2: Bitwise OR convolution

Exercise 3: Bitwise AND convolution

**Exercise 4: An operation that ORs the first bit, ANDs the second bit, and then repeats.****Exercise 5: An operation that ORs the first bit, ANDs the second bit, XORs the third one, and then repeats.**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 , the vector , where is the convolution operation of the respective subtask. **Please output these numbers modulo .**

#### 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 . Let denote the convolution operation.

, so add to .

, so add to .

, so add to .

, so add to .

We already see from above that

## Comments