Encrypting Messages

题意翻译

给定一个长度为 $n$ 的序列 $a$ 和一个长度为 $m$ 的序列 $b$ 以及一个模数 $c$ （保证 $m \le n$ ），你需要对它们进行 $n-m+1$ 次操作。 对于第 $i$ 次操作，将 $a_i \sim a_{i+m-1}$ 对应的加上 $b_1 \sim b_m$ （即 $a_i=a_i+b_1,a_{i+1}=a_{i+1}+b_2$，以此类推 。） 最后，你需要输出操作完成后 $a$ 序列对于 $c$ 取模的结果。 ## 输入格式 第一行输入 $n,m,c$ 下面两行分别是序列 $a$ 与 $b$。 ## 输出格式 输出一行 $n$ 个整数，表示操作完成后 $a$ 序列对于 $c$ 取模的结果。 $\mathtt{Translated\ by}$ @[$\texttt{wkjwkj}$](/user/240405)

题目描述

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.

输入输出样例

输入样例 #1

4 3 2
1 1 1 1
1 1 1

输出样例 #1

0 1 1 0

输入样例 #2

3 1 5
1 2 3
4

输出样例 #2

0 1 2

说明

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.