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 a1, a2, ..., an. Encryption uses a key which is a sequence of m integers b1, b2, ..., bm (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 a1, a2, ..., am a corresponding number b1, b2, ..., bm. On the second step we add to each number a2, a3, ..., am + 1 (changed on the previous step) a corresponding number b1, b2, ..., bm. And so on: on step number i we add to each number ai, ai + 1, ..., ai + m - 1 a corresponding number b1, b2, ..., bm. The result of the encryption is the sequence a1, a2, ..., an after n - m + 1 steps.

Help the Beaver to write a program that will encrypt messages in the described manner.

Input

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 ≤ 103
  * 1 ≤ c ≤ 103



The input limitations for getting 100 points are: 

  * 1 ≤ m ≤ n ≤ 105
  * 1 ≤ c ≤ 103

Output

Print n space-separated integers — the result of encrypting the original message.

Examples

Input

4 3 2
1 1 1 1
1 1 1


Output

0 1 1 0


Input

3 1 5
1 2 3
4


Output

0 1 2

Note

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. 
'''p=input().rstrip().split(' ')
A=int(p[0])
l=['a','b']
if A>2:
    a='b'
    b='a';
    for i in range(2,A):
        c=l[i-1]+l[i-2];
        l.append(c)
C=list(l[A-1])
print(C)
for i in range(0,int(p[1])):
    s=input().rstrip()
    t=len(s)
    if t>len(C):
        print(0%1000000007)
    elif t==len(C):
        if s==''.join(C):
            print(1)
        else:
            print(0%1000000007)
    else:
        V=0;
        for j in range(0,len(C)-t+1):
            G=C[j:j+t]
            if ''.join(G)==s:
                V=(V+1)%1000000007;
        print(V%1000000007)
n=int(input())
if n%2!=0:
    print(n+1)
else:
    f=n;
    while(n%2==0):
        f+=(n//2)
        n=n//2;
    if n!=1:
        f+=1;
    print(f)'''


p=input().rstrip().split(' ')
n=int(p[0])
m=int(p[1])
c=int(p[2])
r=input().rstrip().split(' ')
s=input().rstrip().split(' ')
for i in range(0,n-m+1):
    A=0;
    for j in range(i,m+i):
        r[j]=(int(r[j])+int(s[A]))%c
        A+=1;
print(*r)
