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.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.StringTokenizer;
public class cf177d {
  public static void main(String[] args) {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int n = in.nextInt();
    int m = in.nextInt();
    int c = in.nextInt();
    int[] v = new int[n];
    int[] w = new int[m];
    for(int i=0; i<n; i++)
      v[i] = in.nextInt();
    for(int i=0; i<m; i++)
      w[i] = in.nextInt();
    int add = 0;
    for(int i=0; i<n; i++) {
      if(i < m) add += w[i];
      if(n-i < m) add -= w[m-(n-i)-1];
      v[i] += add;
      out.print(v[i]%c+" ");
    }
    out.close();
  }
  static class FastScanner {
    BufferedReader br;
    StringTokenizer st;
    
    public FastScanner(InputStream in) {
      br = new BufferedReader(new InputStreamReader(in));
      scanLine();
    }
    public void scanLine() {
      try {
        st = new StringTokenizer(br.readLine().trim());
      } catch(Exception e) {
        throw new RuntimeException(e.getMessage());
      }
    }
    public int numTokens() {
      if(!st.hasMoreTokens()) {
        scanLine();
        return numTokens();
      }
      return st.countTokens();
    }
    public String next() {
      if(!st.hasMoreTokens()) {
        scanLine();
        return next();
      }
      return st.nextToken();
    }
    public double nextDouble() {
      return Double.parseDouble(next());
    }
    public long nextLong() {
      return Long.parseLong(next());
    }
    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}
