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

public class Solution {
    //<editor-fold desc="input parse" defaultstate="collapsed">

    private static StringTokenizer st;
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    private static long nextLong() {
        return Long.parseLong(st.nextToken());
    }

    private static int nextInt() {
        return Integer.parseInt(st.nextToken());
    }

    private static double nextDouble() {
        return Double.parseDouble(st.nextToken());
    }

    private static short nextShort() {
        return Short.parseShort(st.nextToken());
    }

    private static byte nextByte() {
        return Byte.parseByte(st.nextToken());
    }

    private static void initTokenizer() throws Exception {
        st = new StringTokenizer(reader.readLine());
    }

    //</editor-fold>

    private static class Tree {
        private int[] a;

        private int[] tree;

        public Tree (int[] a) {
            this.a = a;

            tree = new int[(a.length << 2) + 1];
        }

        public void add(int l, int r, int val) {
            this.add(0, l, r, 0, a.length - 1, val);
        }

        private void add(int node, int l, int r, int lborder, int rborder, int val) {
            if (l == lborder && r == rborder) {
                tree[node] += val;
                return;
            }

            int mid = (lborder + rborder) >> 1;

            int ch1 = (node << 1) + 1;
            int ch2 = ch1 + 1;

            if (l > mid) {
                add(ch2, l, r, mid + 1, rborder, val);
                return;
            }

            if (r <= mid) {
                add(ch1, l, r, lborder, mid, val);
                return;
            }

            add(ch1, l, mid, lborder, mid, val);
            add(ch2, mid + 1, r, mid + 1, rborder, val);
        }

        public int get(int i) {
            int value = a[i];

            int lborder = 0;
            int rborder = a.length - 1;

            int node = 0;

            value += tree[0];

            while (lborder < rborder) {
                int mid = (lborder + rborder) >> 1;

                if (i <= mid) {
                    node = (node << 1) + 1;
                    value += tree[node];
                    rborder = mid;
                }
                else {
                    node = (node << 1) + 2;
                    value += tree[node];
                    lborder = mid + 1;
                }
            }

            return value;
        }
    }

    public static void main(String[] args) throws Exception {
        initTokenizer();

        int asize = nextInt();
        int bsize = nextInt();
        int cmod = nextInt();

        int[] a = new int[asize];

        initTokenizer();
        for (int i = 0; i < a.length; i++) {
            a[i] = nextInt();
        }

        int[] b = new int[bsize];
        initTokenizer();

        for (int i = 0; i < b.length; i++) {
            b[i] = nextInt();
        }

        Tree tree = new Tree(a);

        for (int i = 0; i < b.length; i++) {
            tree.add(i, a.length - (b.length - i), b[i]);
        }

        for (int i = 0; i < a.length; i++) {
            int val = tree.get(i);

            val %= cmod;

            System.out.print(val + " ");
        }
    }
}