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



import java.io.*;

public class Main{

    public static void main(String[] args) {

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();
        
          }



    static class Solver {


        class Node implements Comparable<Node>{
            int i;
            long c;
          
            Node(int i,long c)
            {
                this.i=i;
                this.c=c;
                

            }

           public int compareTo(Node n)
            {
                return Long.compare(this.c, n.c);
            }
        }

        public boolean done(int[] sp,int[] par)
        {
            int root;

            root=findSet(sp[0],par);
            
           for(int i=1;i<sp.length;i++)
           {
                if(root!=findSet(sp[i], par))
                    return false;
           }
           return true;
        }
       public int findSet(int i,int[] par)
       {
           int x =i;
            boolean flag =false;
            while(par[i]>=0)
            {
                flag = true;
                i=par[i];
            }
            if(flag)
                par[x]=i;
            return i;
       }

       public void unionSet(int i,int j,int[] par)
       {
            int x = findSet(i, par);
            int y = findSet(j, par);
            par[y] = x; 
       }

       public  long pow(long a, long b, long MOD) {
            if (b == 0) {
                return 1;
            }
            if (b == 1) {
                return a;
            }
            long val = pow(a, b / 2, MOD);
            if (b % 2 == 0) {
                return val * val % MOD;
            } else {
                return val * (val * a % MOD) % MOD;

            }
           
        }


        public void minPrimeFactor(int n,int[] s)
        {
            boolean prime[] = new boolean[n+1];
            Arrays.fill(prime, true);
            s[1]=1;
            s[2]=2;
            for(int i=4;i<=n;i+=2)
            {
                prime[i]=false;
                s[i]=2;
            }

            for(int i=3;i<=n;i+=2)
            {
                if(prime[i])
                {
                    s[i]=i;
                    for(int j=2*i;j<=n;j+=i)
                    {
                        prime[j]=false;
                        s[j]=i;
                    }
                }
            }
            
        }

        
        public void findAllPrime(int n,ArrayList<Node> al,int s[])
        {
            int curr = s[n];
            int cnt = 1;
            while(n>1)
            {
                n/=s[n];
                if(curr==s[n])
                {
                    cnt++;
                    continue;

                }
                Node n1 = new Node(curr,cnt);
                al.add(n1);

                curr=s[n];
                cnt=1;
            }
        }

        

        public int binarySearch(int n,int k)
        {
            int left=1;
            int right=100000000+5;
            int ans=0;
            while(left<=right)
            {
                int mid = (left+right)/2;
                if(n/mid>=k)
                {
                    left = mid+1;
                    ans=mid;
                }
                else
                {
                    right=mid-1;
                }
            }

            return ans;
        }
        public boolean checkPallindrom(String s)
        {
            char ch[] = s.toCharArray();

            for(int i=0;i<s.length()/2;i++)
            {
                if(ch[i]!=ch[s.length()-1-i])
                    return false;
            }
            return true;
        }


        public void dfs_util(ArrayList<Integer>[] al,boolean vis[],int x,int cnt[],int sts[],int fts[],ArrayList<Integer> fi)
        {
               vis[x] = true;
               fi.add(x);
                sts[cnt[0]]=x+1;
                boolean flag = false;
                for(int i=0;i<al[x].size();i++)
                {
                    if(!vis[al[x].get(i)])
                    {   flag =true;
                        cnt[0]++;
                        dfs_util(al, vis, al[x].get(i),cnt,sts,fts,fi);
                    }    
                    
                }
            
            cnt[0]++;
            fts[cnt[0]]=x+1;
            return;
        }

        public void dfs(ArrayList[] al,int sts[],int fts[],ArrayList<Integer> fi)
        {
            int count[]=new int[1];
            count[0]=0;
           boolean vis[] = new boolean[al.length];
           for(int i=0;i<al.length;i++)
           {
                if(!vis[i])
                {
                    count[0]++;
                    dfs_util(al,vis,i,count,sts,fts,fi);
                }
           }
        }
   
        public void remove(ArrayList<Integer>[] al,int x)
        {
            for(int i=0;i<al.length;i++)
            {
                for(int j=0;j<al[i].size();j++)
                {
                    if(al[i].get(j)==x)
                        al[i].remove(j);

                }
            }
        }

        private void solve(InputReader inp, PrintWriter out1) {
    
            int n = inp.nextInt();
            int m = inp.nextInt();
            int c = inp.nextInt();
            int arr[] = new int[n];
            int b[] = new int[m];
            for(int i=0;i<n;i++)
            {
                arr[i] = inp.nextInt();
            }

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

            int pre[] = new int[m];

            int suf[] = new int[m];

            pre[0]=b[0];
            for(int i=1;i<m;i++)
            {
                pre[i]=(b[i]+pre[i-1]);
            }
            // out1.println(Arrays.toString(pre));
            suf[m-1]=b[m-1];
            for(int i=m-2;i>=0;i--)
            {
                suf[i]=(suf[i+1]+b[i]);
            }

            // out1.println(Arrays.toString(suf));
            
            for(int i=0;i<=n-m;i++)
            {
                if(i>=0&&i<=m-1)
                {
                    arr[i]=(arr[i]+pre[i])%c;
                    continue;
                }
                arr[i] = (arr[i]+pre[m-1])%c;
            }

            for(int i=n-m+1;i<=n-1;i++)
            {
                
                if(i+1>=m)
                {
                    arr[i] = (arr[i] + suf[i-n+m])%c;
                    
                }
                else
                {
                    arr[i] = (arr[i]+ suf[i-n+m] - suf[i+1])%c;
                }
            }
            
            for(int i=0;i<n;i++)
            {
                out1.print(arr[i]+" ");
            }
        }
}





    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}
class ele{
    long value;
    long i;
    boolean flag;
    public ele(long value,long i)
    {
        this.value = value;
        this.i=i;
        this.flag = false;
    }
}