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 ai (0 ≤ ai c), separated by single spaces — the original message. The third input line contains m integers bi (0 ≤ bi c), separated by single spaces — the encryption key.The input limitations for getting 30 points are: 1 ≤ m ≤ n ≤ 1031 ≤ c ≤ 103The input limitations for getting 100 points are: 1 ≤ m ≤ n ≤ 1051 ≤ c ≤ 103

输出描述:

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.