Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array ai either with ai + x or with ai - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. <image>) can reach, if Maxim would apply no more than k operations to it. Please help him in that.

Input

The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers a1, a2, ..., an (<image>) — the elements of the array found by Maxim.

Output

Print n integers b1, b2, ..., bn in the only line — the array elements after applying no more than k operations to the array. In particular, <image> should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.

Examples

Input

5 3 1
5 4 3 5 2


Output

5 4 3 5 -1 


Input

5 3 1
5 4 3 5 5


Output

5 4 0 5 5 


Input

5 3 1
5 4 4 5 5


Output

5 1 4 5 5 


Input

3 2 7
5 4 2


Output

5 11 -5 
import static java.lang.Math.*;
import static java.util.Arrays.* ;

import java.util.*;
import java.io.*;

public class D
{

    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        PriorityQueue<Pair> neg = new PriorityQueue<>((a , b)-> Long.compare(b.y , a.y)) ;
        PriorityQueue<Pair> pos = new PriorityQueue<>(Comparator.comparingLong(a -> a.y)) ;

        int n = sc.nextInt() ;
        int k = sc.nextInt() ;
        int x = sc.nextInt() ;
        long [] a = new long [n];

        for(int i = 0 ;i < n ; i ++) {
            a[i] = sc.nextInt();
            if(a[i] < 0)
                neg.add(new Pair(i , a[i])) ;
            else
                pos.add(new Pair(i , a[i])) ;
        }

        while (k > 0 && neg.size() % 2 == 0)
        {
            if(!neg.isEmpty() && !pos.isEmpty())
            {
                if(-neg.peek().y > pos.peek().y)
                {
                    Pair p = pos.poll() ;
                    p.y -= x ;
                    if(p.y < 0)
                        neg.add(p) ;
                    else
                        pos.add(p);
                    k -- ;
                }
                else
                {
                    Pair p = neg.poll() ;
                    p.y += x ;
                    if(p.y > 0)
                        pos.add(p) ;
                    else
                        neg.add(p);
                    k -- ;
                }
            }
            else if(!neg.isEmpty())
            {
                Pair p = neg.poll() ;
                p.y += x ;
                if(p.y > 0)
                    pos.add(p) ;
                else
                    neg.add(p) ;
                k -- ;
            }
            else if(!pos.isEmpty())
            {
                Pair p = pos.poll() ;
                p.y -= x ;
                if(p.y < 0)
                    neg.add(p) ;
                else pos.add(p);
                k -- ;
            }

        }

        while (k > 0)
        {
            if(!neg.isEmpty() && !pos.isEmpty())
            {
                if(-neg.peek().y > pos.peek().y)
                {
                    Pair p = pos.poll() ;
                    p.y += x ;
                    pos.add(p) ;
                    k -- ;
                }
                else
                {
                    Pair p = neg.poll() ;
                    p.y -= x ;
                    neg.add(p) ;
                    k -- ;
                }
            }
            else if(!neg.isEmpty())
            {
                Pair p = neg.poll() ;
                p.y -= x ;
                neg.add(p) ;
                k -- ;
            }
            else if(!pos.isEmpty())
            {
                Pair p = pos.poll() ;
                p.y += x ;
                pos.add(p) ;
                k -- ;
            }
        }
        while (!pos.isEmpty())
            a[pos.peek().x] = pos.poll().y ;
        while (!neg.isEmpty())
            a[neg.peek().x] = neg.poll().y ;

        for(long aa : a)
            out.print(aa+" ");

        out.flush();
        out.close();
    }
    class Pair
    {
        int x ;
        long y ;
        Pair(int a , long b)
        {
            x = a ;
            y = b ;
        }
    }
    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        String nextLine() throws Exception
        {
            return br.readLine() ;
        }
        int nextInt() throws Exception { return Integer.parseInt(next()); }

        long nextLong() throws Exception { return Long.parseLong(next()); }

        double nextDouble() throws Exception { return Double.parseDouble(next());}
    }

    public static void main (String [] args) throws Exception
    {
        new D().main();
    }

}