CF177D1.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.

ABBYY 公司的聪明海狸发明了一种新的消息加密方法，现在他想要检验该方法的性能。手动检验耗时且枯燥，因此他决定请 ABBYY 杯的参赛选手们帮忙。

一条消息是一个由 $n$ 个整数组成的序列 $a_1,\,a_2,\,\dots,\,a_n$。加密过程使用一个密钥，该密钥是一个由 $m$ 个整数组成的序列 $b_1,\,b_2,\,\dots,\,b_m$（其中 $m \leq n$）。消息中和密钥中的所有数字均属于区间 $[0,\,c-1]$（含端点），所有运算均在模 $c$ 意义下进行。

加密共进行 $n - m + 1$ 步。第一步中，将 $a_1,\,a_2,\,\dots,\,a_m$ 分别加上对应的 $b_1,\,b_2,\,\dots,\,b_m$；第二步中，将上一步已更新过的 $a_2,\,a_3,\,\dots,\,a_{m+1}$ 分别加上对应的 $b_1,\,b_2,\,\dots,\,b_m$；依此类推：在第 $i$ 步中，将 $a_i,\,a_{i+1},\,\dots,\,a_{i+m-1}$ 分别加上对应的 $b_1,\,b_2,\,\dots,\,b_m$。经过全部 $n - m + 1$ 步后所得的序列 $a_1,\,a_2,\,\dots,\,a_n$ 即为加密结果。

请帮助海狸编写一个程序，按上述方式对消息进行加密。

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 ≤ 103
• 1 ≤ c ≤ 103

The input limitations for getting 100 points are:

• 1 ≤ m ≤ n ≤ 105
• 1 ≤ c ≤ 103

第一行输入包含三个整数 $n$、$m$ 和 $c$，以单个空格分隔。

第二行输入包含 $n$ 个整数 $a_i$（$0 \le a_i < c$），以单个空格分隔——表示原始消息。

第三行输入包含 $m$ 个整数 $b_i$（$0 \le b_i < c$），以单个空格分隔——表示加密密钥。

获得 30 分的输入限制为：

• $1 \le m \le n \le 10^3$
• $1 \le c \le 10^3$

获得 100 分的输入限制为：

• $1 \le m \le n \le 10^5$
• $1 \le c \le 10^3$

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

输出 n 个空格分隔的整数——即原始消息加密后的结果。

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.

在第一个样例中，加密过程分为两步：第一步后，$ a = (0, 0, 0, 1) $（注意所有运算均在模 $ 2 $ 意义下进行），第二步后，$ a = (0, 1, 1, 0) $，即为答案。