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.io.*;

import java.util.*;

public class CodeForces {


	public void solve() throws IOException {
		int n = nextInt();
		int m = nextInt();
		int c = nextInt();
		int arr[]=new int[n];
		int barr[] = new int[m];
		for (int i = 0, l = arr.length; i < l; i++) {
			arr[i]=nextInt()%c;
		}
		for (int i = 0, l = barr.length; i < l; i++) {
			barr[i]=nextInt()%c;
		}
		for(int i=0;i<n-m+1;i++){
			for(int j=0;j<m;j++){
				arr[i+j]+=barr[j];
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0, l = arr.length; i < l; i++) {
			sb.append(arr[i]%c).append(" ");
		}
		out.println(sb.toString());
	}
	
	public static void main(String[] args) {
		new CodeForces().run();
	}

	int NOD(int a, int b) {
		while (a != 0 && b != 0) {
			if (a >= b)
				a = a % b;
			else
				b = b % a;
		}
		return a + b;
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter out;
	boolean isOuterFile = false;

	public void run() {
		try {
			if (isOuterFile) {
				reader = new BufferedReader(new FileReader("input.txt"));
				out = new PrintWriter(new BufferedWriter(new FileWriter(
						"output.txt")));
			} else {
				reader = new BufferedReader(new InputStreamReader(System.in));
				out = new PrintWriter(System.out);
			}

			tokenizer = null;
			//long time = new Date().getTime();
			solve();
			//out.println(time - new Date().getTime());
			reader.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
}