Background

Description

Programmer Xiao Ming is developing a large software system. There is a core routine described by the following pseudocode (assume all variables are initially $0$, and that none of the data types will overflow):

Input a[0], a[1], ... , a[n - 1], b[0], b[1], ... , b[n - 1], C
For i: 0 to n - 1
	x[0, i] = a[i]
For i: 0 to C - 1
	For j: 0 to n - 1
		For k: 0 to n - 1
			x[i + 1, (j + k) mod n] = x[i + 1, (j + k) mod n] + b[k]x[i, j]
Output x[C, 0] mod (n + 1), x[C, 1] mod (n + 1), ... , x[C, n - 1] mod (n + 1)

However, this program is very inefficient; its time complexity is $\Theta(n^2 C)$. He wants you to optimize this program while producing the same output. To make the problem easier, he guarantees that the input $n$ can be written as a product of some positive integers, each no greater than $10$, and that $n + 1$ is prime.

Output Format

Output contains $n$ lines, one number per line. The $i$-th line is the value of $x_{C, i} \bmod (n + 1)$. You should ensure each printed number is between $0$ and $n$ inclusive.

4 1
1 2 3 4
4 3 3 1

2
1
0
2

Hint

There are $10$ test points in total. Constraints:

In all testdata, $a_i$ and $b_i$ do not exceed $10^9$.

Translated by ChatGPT 5