Nick had received an awesome array of integers a=[a_1, a_2, ..., a_n] as a gift for his 5 birthday from his mother. He was already going to explore its various properties but after unpacking he was disappointed a lot because the product a_1 ⋅ a_2 ⋅ ... a_n of its elements seemed to him not large enough.

He was ready to throw out the array, but his mother reassured him. She told him, that array would not be spoiled after the following operation: choose any index i (1 ≤ i ≤ n) and do a_i := -a_i - 1.

For example, he can change array [3, -1, -4, 1] to an array [-4, -1, 3, 1] after applying this operation to elements with indices i=1 and i=3. 

Kolya had immediately understood that sometimes it's possible to increase the product of integers of the array a lot. Now he has decided that he wants to get an array with the maximal possible product of integers using only this operation with its elements (possibly zero, one or more times, as many as he wants), it is not forbidden to do this operation several times for the same index. 

Help Kolya and print the array with the maximal possible product of elements a_1 ⋅ a_2 ⋅ ... a_n which can be received using only this operation in some order.

If there are multiple answers, print any of them.

Input

The first line contains integer n (1 ≤ n ≤ 10^{5}) — number of integers in the array.

The second line contains n integers a_1, a_2, …, a_n (-10^{6} ≤ a_i ≤ 10^{6}) — elements of the array

Output

Print n numbers — elements of the array with the maximal possible product of elements which can be received using only this operation in some order from the given array.

If there are multiple answers, print any of them.

Examples

Input


4
2 2 2 2


Output


-3 -3 -3 -3 

Input


1
0


Output


0 

Input


3
-3 -3 2


Output


-3 -3 2 

/*
9 2
        1 1 1 1 1 0 0 0 0
        1 2
        1 5
        5 6
        5 7
        2 3
        2 4
        3 8
        3 9
*/


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Question {


    static LinkedList<Integer> adj[];
    static boolean[] visited;
    static boolean[] visited_;
    static int[] ans;
    static int count_ = 0;
    static final int MAX_SIZE = 1000001;
    static Vector<Boolean> isprime = new Vector<>(MAX_SIZE);
    static Vector<Integer> prime = new Vector<>();
    static Vector<Integer> SPF = new Vector<>(MAX_SIZE);

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        int n = Reader.nextInt();
        int[][] arr = new int[n][2];
        int neg = 0;
        int zero = 0;
        int pos = 0;
        int negMin =0;
        for (int i = 0 ; i < arr.length ; i++){
            arr[i][0] = Reader.nextInt();
            arr[i][1] = i;
            if (arr[i][0]<0){
                arr[i][0] = -(arr[i][0]+1);
                neg++;
            }
            else if (arr[i][0]==0){
                zero++;
            }
            else if (arr[i][0]>0){
                pos++;
            }
        }
        sortbyColumn(arr,0);
        if (zero%2==0 && (neg+pos)%2==0){
            for (int i = 0 ; i < n ;i++){
                arr[i][0] = -(arr[i][0]+1);
            }
        }
        else if (zero%2==1 && (neg+pos)%2==1){
            for (int i = 0 ; i < n ;i++){
                arr[i][0] = -(arr[i][0]+1);
            }
        }
        else if (zero%2==0 && (neg+pos)%2==1){
            for (int i = 0 ; i < zero ; i++){
                arr[i][0] = -(arr[i][0]+1);
            }
            for (int i = zero ; i < n-1 ; i++){
                arr[i][0] = -(arr[i][0] + 1);
            }
        }
        else {
            for (int i = 0 ; i < zero -1 ; i++){
                arr[i][0] = -1;
            }
            if (neg+pos>0){
                arr[zero-1][0] = -1;
                for (int i = zero ; i < n-1; i++){
                    arr[i][0] = -(arr[i][0]+1);
                }
            }
        }

        sortbyColumn(arr,1);
        for (int i = 0 ; i < n ; i++){
            System.out.print(arr[i][0] + " ");
        }









    }
    public static void sortbyColumn(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return 1;
                else
                    return -1;
            }
        });  // End of function call sort().
    }
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    static long phi(long n,long R)
    {

        long result = R;


        for (long p = 2; p * p <= n; ++p)
        {


            if (n % p == 0)
            {


                while (n % p == 0)
                    n =n/p;
                result =result - ( result / p);
            }
        }


        //System.out.println("n" + n);
        if (n > 1)
            result -= result / n;
        return result;
    }
}

class person{
    int index;
    int money;

    public person(int index, int money) {
        this.index = index;
        this.money = money;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public void setMoney(int money) {
        this.money = money;
    }

    public int getIndex() {
        return index;
    }

    public int getMoney() {
        return money;
    }
}

class StudentComparator implements Comparator<person>{

    // Overriding compare()method of Comparator
    // for descending order of cgpa
    public int compare(person s1, person s2) {
        if (s1.money > s2.money)
            return 1;
        else if (s1.money < s2.money) {
            return -1;
        }
        else{
            if (s1.index >s2.index){
                return 1;
            }
            else{
                return -1;
            }
        }

    }
}


