A8525. 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.
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}$
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.