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