Programmer Xiao Ming is developing a large-scale software system. The software contains a core program, described by the following pseudocode (assume all variables are initialized to 0, and assume no data type overflow occurs):
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, with a time complexity as high as $\Theta(Cn^2)$. He wants you to help optimize this program, while ensuring the same output is produced. To simplify the problem, he guarantees that the input $n$ can be expressed as a product of several positive integers not exceeding 10, and that $n+1$ is a prime number.
Input
The input file optimize.in contains two non-negative integers $n, C$ on the first line. The next line contains $n$ non-negative integers $a[0], a[1], \dots, a[n-1]$. The third line contains $n$ non-negative integers $b[0], b[1], \dots, b[n-1]$.
Output
The output file optimize.out contains $n$ lines, each containing one number. The $i$-th line is the value of $x[C, i] \pmod{n+1}$. You must ensure the output numbers are between $0$ and $n$.
Constraints
There are a total of 10 test cases. The data ranges are as follows:
| Test Case | $N$ | $C$ |
|---|---|---|
| 1 | $\le 100$ | $\le 100$ |
| 2 | $\le 100$ | $\le 10^9$ |
| 3 | $\le 700$ | $\le 10^9$ |
| 4 | $\le 700$ | $\le 10^9$ |
| 5 | $\le 10^4$ | $= 1$ |
| 6 | $\le 10^5$ | $= 1$ |
| 7 | $\le 10^5$ | $= 1$ |
| 8 | $\le 5 \times 10^5$ | $\le 10^9$ |
| 9 | $\le 5 \times 10^5$ | $\le 10^9$ |
| 10 | $\le 5 \times 10^5$ | $\le 10^9$ |
In all input data, $a[i]$ and $b[i]$ do not exceed $10^9$.
Examples
Input 1
4 1 1 2 3 4 4 3 3 1
Output 1
2 1 0 0