J. Rolling Encryption
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Leroy has been given a sequence of $$$n$$$ integers $$$X$$$ between $$$0$$$ and $$$k - 1$$$ (inclusive) for some positive integer $$$k$$$ which is vital to national security. He doesn't want to write down the numbers themselves in case they fall into the wrong hands so he decides to use a new technique: the 'rolling encryption' to obfuscate the true numbers until he gets safely to his destination.

The rolling encryption technique takes the $$$n$$$ integers and picks a sequence of $$$m$$$ additional integers $$$Y$$$ known as the encryption key (where $$$m \leq n$$$ and each of the $$$m$$$ integers are also between $$$0$$$ and $$$k - 1$$$ inclusive). It takes $$$n - m + 1$$$ steps to encrypt all the numbers and on each step $$$i$$$ (for $$$1 \leq i \leq n - m + 1$$$), the algorithm takes the numbers $$$x_{i}, x_{i + 1}, \dots, x_{i + m - 1}$$$ and adds $$$y_1, y_2, \dots y_m$$$ respectively to each number (so $$$x_{i} = x_{i} + y_{1}$$$, $$$x_{i + 1} = x_{i + 1} + y_{2}$$$, and so on and so forth). Leroy realizes that this technique can cause the numbers to be very big so he decides to do all of the operations modulo $$$k$$$.

Given $$$X$$$ (the sequence of $$$n$$$ integers to encrypt) and $$$Y$$$ (the sequence of $$$m$$$ integers which is the encryption key), Leroy wants your help to compute the new encrypted sequence.

Input

The first line of input will give you three space-separated $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq m \leq n \leq 10^{3}$$$ and $$$1 \leq k \leq 10^{3}$$$) where $$$n$$$ is the length of the original sequence, $$$m$$$ is the length of the encryption key, and $$$k$$$ is the range of the integers.

The next line of input will have $$$n$$$ space-separated integers representing the numbers in the original sequence $$$X$$$ ($$$0 \leq X_{i} \leq k - 1$$$ for all $$$1 \leq i \leq n$$$).

The final line of input will have $$$m$$$ space-separated integers representing the numbers in the encryption key sequence $$$Y$$$ ($$$0 \leq Y_{i} \leq k - 1$$$ for all $$$1 \leq i \leq m$$$).

Output

Output $$$n$$$ space-separated integers, the result of doing the rolling encryption on the original $$$X$$$ sequence.

Example
Input
4 2 3
2 0 1 2
1 0
Output
0 1 2 2
Note

In the first sample, after the first step $$$X = [0, 0, 1, 2]$$$, after the second step $$$X = [0, 1, 1, 2]$$$, after the third step $$$X = [0, 1, 2, 2]$$$ and there are no more steps $$$(n - m + 1) = (4 - 2 + 1)$$$ and so the final answer is $$$[0, 1, 2, 2]$$$.