CF177D2.Encrypting Messages

The Smart Beaver from ABBYY invented a new message encryption method and now wants to check its performance. Checking it manually is long and tiresome, so he decided to ask the ABBYY Cup contestants for help.

A message is a sequence of $n$ integers $a_{1},a_{2},...,a_{n}$ . Encryption uses a key which is a sequence of $m$ integers $b_{1},b_{2},...,b_{m}$ ( $m<=n$ ). All numbers from the message and from the key belong to the interval from $0$ to $c-1$ , inclusive, and all the calculations are performed modulo $c$ .

Encryption is performed in $n-m+1$ steps. On the first step we add to each number $a_{1},a_{2},...,a_{m}$ a corresponding number $b_{1},b_{2},...,b_{m}$ . On the second step we add to each number $a_{2},a_{3},...,a_{m+1}$ (changed on the previous step) a corresponding number $b_{1},b_{2},...,b_{m}$ . And so on: on step number $i$ we add to each number $a_{i},a_{i+1},...,a_{i+m-1}$ a corresponding number $b_{1},b_{2},...,b_{m}$ . The result of the encryption is the sequence $a_{1},a_{2},...,a_{n}$ after $n-m+1$ steps.

Help the Beaver to write a program that will encrypt messages in the described manner.

The first input line contains three integers $n$ , $m$ and $c$ , separated by single spaces.

The second input line contains $n$ integers $a_{i}$ ( $0<=a_{i}<c$ ), separated by single spaces — the original message.

The third input line contains $m$ integers $b_{i}$ ( $0<=b_{i}<c$ ), separated by single spaces — the encryption key.

The input limitations for getting 30 points are:

• $1<=m<=n<=10^{3}$
• $1<=c<=10^{3}$

The input limitations for getting 100 points are:

• $1<=m<=n<=10^{5}$
• $1<=c<=10^{3}$

Print $n$ space-separated integers — the result of encrypting the original message.

In the first sample the encryption is performed in two steps: after the first step $a=(0,0,0,1)$ (remember that the calculations are performed modulo 2), after the second step $a=(0,1,1,0)$ , and that is the answer.