Problem: Another Codeforces Round has just finished! It has gathered n participants, and according to the results, the expected rating change of participant i is a_i. These rating changes are perfectly balanced — their sum is equal to 0.

Unfortunately, due to minor technical glitches, the round is declared semi-rated. It means that all rating changes must be divided by two.

There are two conditions though: 

  * For each participant i, their modified rating change b_i must be integer, and as close to (a_i)/(2) as possible. It means that either b_i = ⌊ (a_i)/(2) ⌋ or b_i = ⌈ (a_i)/(2) ⌉. In particular, if a_i is even, b_i = (a_i)/(2). Here ⌊ x ⌋ denotes rounding down to the largest integer not greater than x, and ⌈ x ⌉ denotes rounding up to the smallest integer not smaller than x. 
  * The modified rating changes must be perfectly balanced — their sum must be equal to 0. 



Can you help with that?

Input

The first line contains a single integer n (2 ≤ n ≤ 13 845), denoting the number of participants.

Each of the next n lines contains a single integer a_i (-336 ≤ a_i ≤ 1164), denoting the rating change of the i-th participant.

The sum of all a_i is equal to 0.

Output

Output n integers b_i, each denoting the modified rating change of the i-th participant in order of input.

For any i, it must be true that either b_i = ⌊ (a_i)/(2) ⌋ or b_i = ⌈ (a_i)/(2) ⌉. The sum of all b_i must be equal to 0.

If there are multiple solutions, print any. We can show that a solution exists for any valid input.

Examples

Input


3
10
-5
-5


Output


5
-2
-3


Input


7
-7
-29
0
3
24
-29
38


Output


-3
-15
0
2
12
-15
19

Note

In the first example, b_1 = 5, b_2 = -3 and b_3 = -2 is another correct solution.

In the second example there are 6 possible solutions, one of them is shown in the example output.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main
{
    public static void main(String[] args){
        new Thread(null, new Runnable() {
            public void run() {
                solve();
            }
        }, "1", 1 << 26).start();
    }
    static void solve () {
        FastReader fr =new FastReader();    PrintWriter op =new PrintWriter(System.out);
        int n =fr.nextInt() ,arr[] =new int[n] ,i ,j =0 ,ans[][] =new int[n][2] ;

        for (i =0 ; i<n ; i++) {    arr[i] =fr.nextInt() ;ans[i][0] =arr[i] ;   ans[i][1] =i ;  }   
        sort (ans , 0 , n-1) ;

        for (i =0 ; i<n ; i++) {
            j += ans[i][0]/2 ;  ans[i][0] /= 2 ;
        }
        if (j != 0) {
            int l =0 ,r =n-1 ;

            while (j>0) {
                if ((arr[ans[l][1]]&1) == 1) {
                    ans[l][0]-- ;  --j ;
                }l++;
            }
            while (j<0) {
                if ((arr[ans[r][1]]&1) == 1) {
                    ans[r][0]++ ;    ++j ;
                }r-- ;
            }
        }
        for (i =0 ; i<n ; ++i)  arr[ans[i][1]] =ans[i][0] ;
        for (i =0 ; i<n ; ++i)    op.println(arr[i]) ;
        op.flush();    op.close();
    }
    public static void sort(int[][] arr , int l , int u)
    {
        int m ;
 
        if(l < u){
            m =(l + u)/2 ;
 
            sort(arr , l , m);  sort(arr , m + 1 , u);
 
            merge(arr , l , m , u);
        }
    } 
    public static void merge(int[][]arr , int l , int m , int u)
    {
        int[][] low = new int[m - l + 1][2];
 
        int[][] upr = new int[u - m][2];
 
        int i ,j =0 ,k =0 ;
 
        for(i =l;i<=m;i++){
            low[i - l][0] =arr[i][0];
            low[i - l][1] =arr[i][1];
        }
 
        for(i =m + 1;i<=u;i++){
            upr[i - m - 1][0] =arr[i][0];
            upr[i - m - 1][1] =arr[i][1];
        }
 
        i =l;
 
        while((j < low.length) && (k < upr.length))
        {
            if(low[j][0] < upr[k][0])
            {
                arr[i][0] =low[j][0];
                arr[i++][1] =low[j++][1];
            }
            else
            {
                if(low[j][0] > upr[k][0])
                {
                    arr[i][0] =upr[k][0];
                    arr[i++][1] =upr[k++][1];
                }
                else
                {
                    if(low[j][1] < upr[k][1])
                    {
                        arr[i][0] =low[j][0];
                        arr[i++][1] =low[j++][1];
                    }
                    else
                    {
                        arr[i][0] =upr[k][0];
                        arr[i++][1] =upr[k++][1];
                    }
                }
            }
        }
 
        while(j < low.length)
        {
            arr[i][0] =low[j][0];
            arr[i++][1] =low[j++][1];
        }
 
        while(k < upr.length)
        {
            arr[i][0] =upr[k][0];
            arr[i++][1] =upr[k++][1];
        }
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br =new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st==null || (!st.hasMoreElements())) 
            {
                try
                {
                    st =new StringTokenizer(br.readLine());
                }
                catch(IOException e)
                {
                    e.printStackTrace();
                }
                
            }
            return st.nextToken();
        }

        String nextLine() {
            String str ="";

            try
            {
                str =br.readLine();
            }
            catch(IOException e)
            {
                e.printStackTrace();
            }

            return str;
        }

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

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