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.Scanner;
import java.io.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author hheng
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD1 solver = new TaskD1();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD1 {
	public void solve(int testNumber, Scanner in, PrintWriter out) {
        int n = in.nextInt(), m = in.nextInt(), c = in.nextInt();
        long[] msg = new long[n];
        long[] key = new long[m];
        long[] front = new long[m];
        long[] back = new long[m];
        for (int i=0; i<n; i++) msg[i] = in.nextLong();
        for (int i=0; i<m; i++) key[i] = in.nextLong();
        
        /*long[] msgcop = new long[n];
        for (int i=0; i<n; i++) msgcop[i] = msg[i];
        for (int i=0; i<n; i++) {
            if (i+m-1 >= n) break;
            for (int j=0; j<m; j++) 
                if (i+j < n) {
                    msgcop[i+j] = (msgcop[i+j] + key[j]) % c;
                    //System.out.print(msg[i+j] +" ");
                }
            //System.out.println();
        }
        for (int i=0; i<n; i++) System.out.print(msgcop[i] + " ");
        System.out.println();*/
        if (m!=n) {
            int steps = n - m + 1;
            front[0] = key[0] % c;
            back[0] = key[m-1] % c;
            for (int i=1; i<m; i++) {
                front[i] = front[i-1] + key[i];
                if (i >= steps) front[i] =  (front[i] - key[i-steps]);
                back[i] = back[i-1] + key[m-i-1];
                if (i >= steps) back[i] = (back[i] - key[m-i+steps-1]);
            }
            
            //for (int i=0; i<m; i++) System.out.println(i+" "+front[i] + " "+back[i]);
            for (int i=0; i<n/2; i++) {
                msg[i] = (msg[i] + front[Math.min(i, m-1)])  % c;
                msg[n-i-1] = (msg[n-i-1] + back[Math.min(i, m-1)]) % c;
                //System.out.println(msg[i] + " "+ msg[n-i-1]);
            }
            if (n%2 == 1) msg[n/2] = (msg[n/2] + front[Math.min(n/2, m-1)]) % c;
        } else {
            for (int i=0; i<n; i++) msg[i] = (msg[i] + key[i]) % c;
        }
        StringBuffer res = new StringBuffer();
        for (int i=0; i<n; i++) res.append(msg[i] + " ");
        out.println(res.toString().trim());

        /*boolean ok = true;
        for (int i=0; i<n; i++)
            if (msgcop[i] != msg[i]) { ok = false; System.out.println("FALSE");  break; }
        if (ok) System.out.println("OK");  */
	}
}
