Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D2. Encrypting Messages

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

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}

Output

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

Examples

Input

4 3 2

1 1 1 1

1 1 1

Output

0 1 1 0

Input

3 1 5

1 2 3

4

Output

0 1 2

Note

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2021 08:30:19 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|