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 codeKNIGHT
 */
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);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
	public void solve(int testNumber, Scanner in, PrintWriter out) {
        int n=in.nextInt(),m=in.nextInt(),c=in.nextInt(),i,j;
        long array[]=new long[n];
        long b[]=new long[m];
        for(i=0;i<n;i++)
            array[i]=in.nextInt();
        long sum=0;
        for(i=0;i<m;i++)
        {
            b[i]=in.nextInt();
            sum+=b[i];
        }

        long forward[]=new long[m];
        forward[0]=b[0];
        for(i=1;i<m;i++)
        {
            forward[i]=forward[i-1]+b[i];
            //System.out.print(forward[i]+ " ");
        }
         long reverse[]=new long[m];
        reverse[0]=sum;
        for(i=1;i<m;i++)
            reverse[i]=reverse[i-1]-b[i-1];

        if(n-m>m-1)
        {
            for(i=0;i<m-1;i++)
                array[i]+=forward[i];
            for(i=n-m;i<n;i++)
                array[i]+=reverse[i-(n-m)];
            for(i=m-1;i<n-m;i++)
                array[i]+=sum;
        }
        else
        {
            for(i=0;i<n-m;i++)
                array[i]+=forward[i];
            for(i=m;i<n;i++)
                array[i]+=reverse[i-(n-m)];
            array[n-m]+=forward[n-m];
            for(i=n-m+1;i<m;i++)
            {
                array[i]+=forward[i]-forward[i-(n-m+1)];
            }
        }
        for(i=0;i<n;i++)
        {
            array[i]%=c;
            if(i<n-1)
            out.print(array[i]+" ");
            else out.println(array[i]);

        }

	}
}

