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:
// @uthor -: puneet
// TimeStamp -: 8:01 PM - 16/10/19 

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.List;

public class Q1 implements Runnable {


    public void solve() {
        int n=in.ni();
        boolean isok=false;
        int sum=0;
        int[] arr=in.intarr(n);
        ArrayList<Integer> list=new ArrayList<>();

        boolean isOk=false;
        for(int i=0;i<n;++i){
            if(Math.abs(arr[i])%2==0){
                out.println(arr[i]/2);
                continue;
            }

            if(arr[i]>0){
                if(isOk){
                    int temp=(arr[i]/2);
                    out.println(temp+1);
                    isOk=false;
                }else {
                    out.println(arr[i]/2);
                    isOk=true;
                }

            }else {
                if(isOk){
                    out.println(arr[i]/2);
                    isOk=false;
                }else {
                    int temp=(arr[i]/2);
                    out.println(temp-1);
                    isOk=true;
                }
            }
        }


//        out.println(sum);
    }

    /* -------------------- Templates and Input Classes -------------------------------*/

    @Override
    public void run() {
        try {
            init();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        solve();
        out.flush();
    }

    private FastInput in;
    private PrintWriter out;

    public static void main(String[] args) throws Exception {
        new Thread(null, new Q1(), "Main", 1 << 27).start();
    }

    private void init() throws FileNotFoundException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        try {
            if (System.getProperty("user.name").equals("puneet")) {
                outputStream = new FileOutputStream("/home/puneet/Desktop/output.txt");
                inputStream = new FileInputStream("/home/puneet/Desktop/input.txt");
            }
        } catch (Exception ignored) {
        }
        out = new PrintWriter(outputStream);
        in = new FastInput(inputStream);
    }

    private void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }

    private void sort(long[] arr) {
        List<Long> list = new ArrayList<>();
        for (long object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }

    public long ModPow(long x, long y, long MOD) {
        long res = 1L;
        x = x % MOD;
        while (y >= 1) {
            if ((y & 1) > 0) res = (res * x) % MOD;
            x = (x * x) % MOD;
            y >>= 1;
        }
        return res;
    }

    public int gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    public long gcd(long a, long b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    static class FastInput {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public FastInput(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int peek() {
            if (numChars == -1) {
                return -1;
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    return -1;
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar];
        }

        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String ns() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private String readLine0() {
            StringBuilder buf = new StringBuilder();
            int c = read();
            while (c != '\n' && c != -1) {
                if (c != '\r') {
                    buf.appendCodePoint(c);
                }
                c = read();
            }
            return buf.toString();
        }

        public String readLine() {
            String s = readLine0();
            while (s.trim().length() == 0) {
                s = readLine0();
            }
            return s;
        }

        public String readLine(boolean ignoreEmptyLines) {
            if (ignoreEmptyLines) {
                return readLine();
            } else {
                return readLine0();
            }
        }

        public BigInteger readBigInteger() {
            try {
                return new BigInteger(ns());
            } catch (NumberFormatException e) {
                throw new InputMismatchException();
            }
        }

        public char nc() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) c;
        }

        public double nd() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, ni());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, ni());
                    }
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }


        public String next() {
            return ns();
        }

        public SpaceCharFilter getFilter() {
            return filter;
        }

        public void setFilter(SpaceCharFilter filter) {
            this.filter = filter;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }

        public int[] intarr(int n) {
            int arr[] = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = ni();
            }
            return arr;
        }

        public double[] doublearr(int n) {
            double arr[] = new double[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nd();
            }
            return arr;
        }

        public double[][] doublearr(int n, int m) {
            double[][] arr = new double[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = nd();
                }
            }
            return arr;
        }

        public int[][] intarr(int n, int m) {
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = ni();
                }
            }
            return arr;
        }


        public long[][] longarr(int n, int m) {
            long[][] arr = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = nl();
                }
            }
            return arr;
        }

        public long[] longarr(int n) {
            long arr[] = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nl();
            }
            return arr;
        }

    }

}