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.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
(n, m, c) = map(int, input().split())
a = list(input().split())
b = list(input().split())
sum = 0
for i in range(n):
	if i < m:
		sum = sum + int(b[i])
		sum = sum % c
	if i >= n - m + 1:
		sum = c - int(b[i - n + m - 1]) + sum
		sum = sum % c
	print((int(a[i]) + sum) % c, end=' ')


(n, m, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pre = [0] * m
suf = [0] * (m + 1)
ans = [0] * n
lp = min(m, n - m + 1)
j = -2
for i in range(m):
	pre[i] = pre[i - 1] + b[i]
for i in range(m - 1, -1, -1):
	suf[i] = suf[i + 1] + b[i]
for i in range(lp):
	ans[i] = (a[i] + pre[i]) % c
if lp == m:
	for i in range(lp, n - lp):
		ans[i] = (a[i] + pre[lp - 1]) % c
else:
	for i in range(lp, n - lp):
		ans[i] = (a[i] + pre[i] - pre[i - lp]) % c
for i in range(n - 1, n - lp - 1, -1):
	ans[i] = (a[i] + suf[j]) % c
	j -= 1
print(*ans)


import sys
from itertools import *
from math import *

def solve():
	(n, m, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	bsum = [0] * m
	for i in range(m):
		bsum[i] = (bsum[i - 1] if i > 0 else 0) + b[i]
	for i in range(n):
		a[i] += bsum[i if i < m else m - 1]
		dont = m - (n - i) - 1
		a[i] -= bsum[dont] if m > dont >= 0 else 0
		a[i] %= c
	print(' '.join(map(str, a)))
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


L = lambda : list(map(int, input().split()))
(n, m, c) = L()
(A, B) = (L(), L())
for i in range(n - m + 1):
	for j in range(i, i + m):
		A[j] += B[j - i]
		A[j] %= c
print(*A)


(n, m, c) = map(int, input().split())
N = list(map(int, input().split()))
M = list(map(int, input().split()))
SM = [0]
for v in M:
	SM += [SM[-1] + v]
answer = []
for (i, v) in enumerate(N):
	if i + len(M) < len(N):
		l = 0
	else:
		l = len(M) - len(N) + i
	if i < len(M):
		r = i
	else:
		r = len(M) - 1
	answer += [(N[i] + SM[r + 1] - SM[l]) % c]
print(' '.join(map(str, answer)))


def sum_mssg(message, encryption, i):
	for j in range(len(encryption)):
		message[i + j] = message[i + j] + encryption[j]
	return message
(n, m, c) = input().split()
n = int(n)
m = int(m)
c = int(c)
message = input().split()
message = [int(i) for i in message]
encryption = input().split()
encryption = [int(i) for i in encryption]
for i in range(n - m + 1):
	message = sum_mssg(message, encryption, i)
for i in range(len(message)):
	message[i] %= c
print(' '.join([str(x) for x in message]))


def solve(n, m, c, a, b):
	for i in range(n - m + 1):
		for j in range(m):
			a[i + j] = (a[i + j] + b[j]) % c
	a = map(str, a)
	return ' '.join(a)
(n, m, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(solve(n, m, c, a, b))


(n, m, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
(s, k) = (0, n - m)
for i in range(n):
	if i < m:
		s += b[i]
	a[i] = (a[i] + s) % c
	if i >= k:
		s -= b[i - k]
print(' '.join((str(i) for i in a)))


(n, m, c) = map(int, input().split())
l = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n - m + 1):
	for j in range(m):
		l[i + j] += b[j]
		l[i + j] %= c
print(*l)


x = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = []
for i in range(len(a) - len(b) + 1):
	for j in range(len(b)):
		a[i + j] = a[i + j] + b[j]
for j in a:
	print(j % x[2], end=' ')


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)


(n, m, c) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
s = 0
for i in range(n):
	if i < m:
		s += b[i]
		s %= c
	if i >= n - m + 1:
		s += c - b[i - n + m - 1]
		s %= c
	print((a[i] + s) % c, end=' ')


(n, m, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sum = 0
x = -(n - m + 2)
for i in range(0, n):
	if i < m:
		sum += b[i]
	x += 1
	if x >= 0:
		sum -= b[x]
	a[i] = (a[i] + sum) % c
print(' '.join((str(i) for i in a)))


from collections import defaultdict
for _ in range(1):
	(n, m, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	cur_sum = 0
	ans = [0] * n
	for (i, j) in enumerate(a):
		if i < m:
			cur_sum += b[i]
			cur_sum %= c
		if n - i < m:
			cur_sum -= b[m - 1 - (n - i)]
			cur_sum %= c
		ans[i] = (j + cur_sum) % c
	print(' '.join([str(i) for i in ans]))


import sys
(n, m, c) = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
sl = 0
sr = 0
Ans = [0] * n
done = False
Sums = []
s = 0
Start = [m - 1] * n
End = [0] * n
for i in range(m):
	Start[i] = i
	s += B[i]
	Sums.append(s)
	End[n - 1 - i] = m - 1 - i
Sums += [0]
for j in range(n):
	s = min(Start[j], End[j])
	e = max(End[j], Start[j])
	Ans[j] = (A[j] + abs(Sums[s - 1] - Sums[e])) % c
ans = ''
for i in range(n - 1):
	ans += str(Ans[i]) + ' '
ans += str(Ans[n - 1])
sys.stdout.write(ans)


(n, m, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for k in range(n - m + 1):
	for i in range(k, k + m):
		a[i] = (a[i] + b[i - k]) % c
print(*a)


(len_message, len_key, mod) = map(int, input().split())
message = list(map(int, input().split()))
key = list(map(int, input().split()))
(sum, low, high) = (0, 0, 0)
result = message[:]
for i in range(len_message):
	if high < len_key:
		sum += key[high]
		high += 1
	if i + len_key > len_message:
		sum -= key[low]
		low += 1
	result[i] = (result[i] + sum) % mod
print(' '.join(map(str, result)))


(a, b, c) = map(int, input().split())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
k = 0
while k < a - b + 1:
	for i in range(0, a):
		for j in range(0, b):
			if j + i < a:
				arr[j + i] = (arr[j + i] + brr[j]) % c
			if i + j == a - 1:
				break
		k = k + 1
		if k > a - b:
			break
for i in range(0, a):
	print(arr[i], end=' ')