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. 
import java.util.*;

import static java.lang.Math.*;
import static java.lang.System.out;


public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main().D();
	}
	
	void D(){
		int n=sc.nextInt(), m=sc.nextInt(), c=sc.nextInt();
		int[] a=new int[n], b=new int[m];
		for(int i=0; i<n; i++)	a[i]=sc.nextInt();
		for(int i=0; i<m; i++)	b[i]=sc.nextInt();
		for(int i=0; i<n-m+1; i++){
			for(int j=0; j<m; j++){
				a[i+j]+= a[i+j]+b[j]<c? b[j]: b[j]-c;
			}
			//a=solveD(a,c);
		}
		out.print(a[0]);
		for(int i=1; i<n; i++){
			out.print(" "+a[i]);
		}
	}
	/*
	int[] solveD(int[] a, int c){
		for(int i=0; i<a.length; i++){
			while(a[i]>=c){
				a[i]-=(c-1);
				if((i+1)<a.length)	a[i+1]++;
			}
		}
		return a;
	}
	*/
	
	void B(){
		int n=sc.nextInt();
		out.println(solveB(n));
	}
	int solveB(int n){
		int a=1;
		if(n%2==0)	a=2;
		else{
			// TLE（2以上で最小の約数の求め方）
			for(int i=3; i<=n; i+=2){
				if(n%i==0){
					a=i;
					break;
				}
			}
		}
		out.print("N"+n+"/A"+a+" ");
		return n>1? n+solveB(n/a): n;
	}
	
	void OldB(){
		int nn=sc.nextInt(), n=nn, c=n,ans=0;
		boolean list[]=new boolean[n+1];
		
		int r=0;
		for(int i=2; i<n; i++){
			if(n%1!=0)	continue;
			n=nn;c=nn;
			Arrays.fill(list, false);
			list[i]=true;
			c+=n/i;
			n=n/i;
			while(n>1){
				for(int j=2; j<=n; j++){
					if(n%j==0 && !list[j]){
						r=j;
						list[r]=true;
						break;
					}
				}
				c+=n/r;
				n=n/r;
			}
			ans=max(c,ans);
		}
		out.println(ans);
	}

	void A(){
		int n=sc.nextInt();
		int[][] a = new int[n][n];
		boolean[][] b = new boolean[n][n];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++)	a[j][i]=sc.nextInt();
		}
		int ans=0;
		for(int i=0,j=0; i<n; i++,j++){
			ans+= b[j][i]? 0: a[j][i];
			b[j][i]=true;
		}
		for(int i=n-1, j=0; j<n; i--,j++){
			ans+= b[j][i]? 0: a[j][i];
			b[j][i]=true;
		}
		int m=(n-1)/2;
		for(int i=0; i<n; i++){
			ans+= b[m][i]? 0: a[m][i];
			b[m][i]=true;
		}
		for(int i=0; i<n; i++){
			ans+= b[i][m]? 0: a[i][m];
			b[i][m]=true;
		}
		out.println(ans);
	}

}
