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.util.*;
import java.io.*;
import java.text.*;
import java.math.*;
import java.lang.Math.*;

public class balanced_rating_changes {
	
	public static void main(String[] args) throws Exception {new balanced_rating_changes().run();}
	public FastIO file = new FastIO();
	public int ntc, ctc;
	public final long MOD = 1000000007L; //998244353L; 
	public final int M0D = 1000000007; //998244353
	public final int N = 200005, dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
	
	public void run() throws Exception {
		ntc = 1; //nextInt();
		for (ctc = 1; ctc <= ntc; ++ctc) solve();
		file.out.flush(); file.out.close();
	}
	
	
	
	void solve() {
		int n = nextInt();
		boolean flag = true;
		for (int i = 0; i < n; i++) {
			int x = nextInt();
			if (x % 2 == 0) println(x / 2);
			else {
				if (flag) {
					if (x > 0) {
						println((x + 1) / 2);
					}
					else {
						println(x / 2);
					}
				}
				else {
					if (x > 0) {
						println(x / 2);
					}
					else {
						println((x - 1) / 2);
					}
				}
				flag ^= true;
			}
		}
	}
	
	void sort(long[] a) { shuffle(a); Arrays.sort(a); }
	void sort(int[] a) { shuffle(a); Arrays.sort(a); }
	void shuffle(long[] a) {
		for (int i = a.length - 1; i >= 0; i--) { int j = (int) (Math.random() * (i + 1)); a[i] ^= a[j] ^ (a[j] = a[i]); } }
	void shuffle(int[] a) {
		for (int i = a.length - 1; i >= 0; i--) { int j = (int) (Math.random() * (i + 1)); a[i] ^= a[j] ^ (a[j] = a[i]); } }
	long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
	long lcm(long x, long y) { return x / gcd(x, y) * y; }
	long mod(long n, long mod) { return (n % mod + mod) % mod; }
	long max(long a, long b) { return Math.max(a, b); }
	int max(int a, int b) { return Math.max(a, b); }
	long min(long a, long b) { return Math.min(a, b); }
	int min(int a, int b) { return Math.min(a, b); }
	long pow(long n, long p, long mod) { long ret = 1L;
	while (p > 0) { if (p % 2 != 0L) ret = mod(ret * n, mod); n = mod(n * n, mod); p >>= 1L; } return ret; }
	long pow(long n, long p) { long ret = 1L;
	while (p > 0) { if (p % 2 != 0L) ret *= n; n *= n; p >>= 1L; } return ret; }
	boolean isPrime(int n) { 
		if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false;
		for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
	String next() {return file.next();}
	int nextInt() {return file.nextInt();}
	long nextLong() {return file.nextLong();}
	double nextDouble() {return file.nextDouble();}
	String nextLine() {return file.nextLine();}
	void print(Object o) {file.out.print(o);}
	void println(Object o) {file.out.println(o);}
	void printf(String s, Object... o) {file.out.printf(s, o);}
	class FastIO {
		BufferedReader br;
		StringTokenizer st;
		PrintWriter out;
		public FastIO() {br = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out);}
		String next() {while (st == null || !st.hasMoreElements()) {try {st = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}}return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine() {String str = "";try {str = br.readLine();} catch (IOException e) {e.printStackTrace();} return str;}
		void print(Object o) {out.print(o);}
		void println(Object o) {out.println(o);}
		void printf(String s, Object... o) {out.printf(s, o);} }
	class Pair<A, B> implements Comparable {
		A fi; B se;
		public Pair(A fi, B se) { this.fi = fi; this.se = se; }
		public boolean equals(Object o) { if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;
		Pair<?, ?> p = (Pair<?, ?>) o; if (!fi.equals(p.fi)) return false; return se.equals(p.se); }
		public int hashCode() { return 31 * fi.hashCode() + se.hashCode(); }
		public String toString() { return fi.toString() + " " + se.toString(); }
		<A, B> Pair<A, B> of(A a, B b) { return new Pair<A, B>(a, b); }
		public int compareTo(Object o) { Pair<?, ?> p = (Pair<?, ?>) o;
		if (fi.equals(p.fi)) return ((Comparable) se).compareTo(p.se); return ((Comparable) fi).compareTo(p.fi); } } }