Repeated Circular Convolution Exponentiation

Given two arrays a and b of length n and an integer C, define a sequence of arrays x[0], x[1], ..., x[C] as follows:

Initialize \[ x[0][i] = a[i] \quad \text{for } i=0,1,\dots,n-1. \]

Then, for \(i = 0, 1, \dots, C-1\), update \[ x[i+1][(j+k) \bmod n] = x[i+1][(j+k) \bmod n] + b[k]\, x[i][j] \quad \text{for all } j,k=0,1,\dots,n-1. \]

Finally, output \[ x[C][0] \bmod (n+1),\; x[C][1] \bmod (n+1),\; \dots,\; x[C][n-1] \bmod (n+1). \]

This process is equivalent to taking a circular convolution power. Let \[ A(x)=a[0]+a[1]x+\cdots+a[n-1]x^{n-1}, \quad B(x)=b[0]+b[1]x+\cdots+b[n-1]x^{n-1}. \] After \(C\) convolutions, we have: \[ \text{Result}(x)=A(x)\cdot B(x)^C \mod (x^n-1). \] Then, each coefficient is taken modulo \(n+1\) where it is given that \(n+1\) is prime. Also, it is guaranteed that n can be factorized as a product of positive integers not exceeding 10. This fact may be used to optimize the algorithm.

Your task is to compute the final sequence as defined above in an efficient manner.

inputFormat

The input consists of four lines:

• The first line contains an integer n (the length of the arrays).
• The second line contains n integers representing array a.
• The third line contains n integers representing array b.
• The fourth line contains an integer C.

outputFormat

Output n space‐separated integers, where the i-th integer is x[C][i] mod (n+1) (for i from 0 to n-1).

sample

3
1 2 3
4 5 6
1

3 3 0