177D1.md (2518B)
1 Source: https://codeforces.com/problemset/problem/177/D1 2 3 D1. Encrypting Messages 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 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*. 24 25 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. 26 27 Help the Beaver to write a program that will encrypt messages in the described manner. 28 29 Input 30 31 The first input line contains three integers *n*, *m* and *c*, separated by single spaces. 32 33 The second input line contains *n* integers *a**i* (0 ≤ *a**i* < *c*), separated by single spaces — the original message. 34 35 The third input line contains *m* integers *b**i* (0 ≤ *b**i* < *c*), separated by single spaces — the encryption key. 36 37 The input limitations for getting 30 points are: 38 39 * 1 ≤ *m* ≤ *n* ≤ 103 40 * 1 ≤ *c* ≤ 103 41 42 The input limitations for getting 100 points are: 43 44 * 1 ≤ *m* ≤ *n* ≤ 105 45 * 1 ≤ *c* ≤ 103 46 47 Output 48 49 Print *n* space-separated integers — the result of encrypting the original message. 50 51 Examples 52 53 Input 54 55 ``` 56 4 3 2 57 1 1 1 1 58 1 1 1 59 ``` 60 61 Output 62 63 ``` 64 0 1 1 0 65 ``` 66 67 Input 68 69 ``` 70 3 1 5 71 1 2 3 72 4 73 ``` 74 75 Output 76 77 ``` 78 0 1 2 79 ``` 80 81 Note 82 83 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.