Problem: Vus the Cossack has n real numbers a_i. It is known that the sum of all numbers is equal to 0. He wants to choose a sequence b the size of which is n such that the sum of all numbers is 0 and each b_i is either ⌊ a_i ⌋ or ⌈ a_i ⌉. In other words, b_i equals a_i rounded up or down. It is not necessary to round to the nearest integer.

For example, if a = [4.58413, 1.22491, -2.10517, -3.70387], then b can be equal, for example, to [4, 2, -2, -4]. 

Note that if a_i is an integer, then there is no difference between ⌊ a_i ⌋ and ⌈ a_i ⌉, b_i will always be equal to a_i.

Help Vus the Cossack find such sequence!

Input

The first line contains one integer n (1 ≤ n ≤ 10^5) — the number of numbers.

Each of the next n lines contains one real number a_i (|a_i| < 10^5). It is guaranteed that each a_i has exactly 5 digits after the decimal point. It is guaranteed that the sum of all the numbers is equal to 0.

Output

In each of the next n lines, print one integer b_i. For each i, |a_i-b_i|<1 must be met.

If there are multiple answers, print any.

Examples

Input


4
4.58413
1.22491
-2.10517
-3.70387


Output


4
2
-2
-4


Input


5
-6.32509
3.30066
-0.93878
2.00000
1.96321


Output


-6
3
-1
2
2

Note

The first example is explained in the legend.

In the second example, we can round the first and fifth numbers up, and the second and third numbers down. We can round the fourth number neither up, nor down.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.text.*;
import java.lang.*;
import java.math.*;
 
public class Main{
	
	static ArrayList a[]=new ArrayList[200001];

	public void solve () {
		InputReader in = new InputReader(System.in);
	    PrintWriter pw = new PrintWriter(System.out); 
	    int n=in.nextInt();
	    double a[]=new double[n];
	    long sum=0L;
	    long ans[]=new long [n];

	    for(int i=0;i<n;i++) {
	    	a[i]=Double.parseDouble(in.nextLine());
	    	if(a[i]<0.0) {
	    		sum+=Math.ceil(a[i]);
	    		ans[i]=(long)Math.ceil(a[i]);;
	    	}
	    	else
	    	{
	    		sum+=Math.floor(a[i]);
	    		ans[i]=(long) Math.floor(a[i]);
	    	}
	    }
	    for(int i=0;i<n && sum!=0 ;i++) {
	    	if(sum>0 && a[i]<0.0) {
	    		ans[i]=(long) Math.floor(a[i]);
		    	sum-=(Math.ceil(a[i])-Math.floor(a[i]));

	    	}
	    	else if(sum<0 && a[i]>0.0){
	    		ans[i]=(long) Math.ceil(a[i]);
		    	sum+=(Math.ceil(a[i])-Math.floor(a[i]));
	    	}
	    	
	    }
	    for(int i=0;i<n;i++) {
	    	pw.println(ans[i]);
	    }
	    
	   
		pw.flush();
		pw.close();
	}
	public static void main(String[] args) throws Exception {
        
        
        new Thread(null,new Runnable() {
        	public void run() {
        		new Main().solve();
        	}
        },"1",1<<26).start();
        
        
    }
    static void debug(Object... o) {
    	System.out.println(Arrays.deepToString(o));
        }
        
        static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        {
            this.stream = stream;
        }
        public int snext() 
        {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() 
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
        public static long mod = 1000000007;
        public static int d;
        public static int p;
        public static int q;
        public void extended(int a,int b) {
        	if(b==0) {
        		d=a;
        		p=1;
        		q=0;
        	}
        	else
        	{
        		extended(b,a%b);
        		int temp=p;
        		p=q;
        		q=temp-(a/b)*q;
        	}
        }
        public static long[] shuffle(long[] a,Random gen)
        {
            int n = a.length;
            for(int i=0;i<n;i++)
            {
                int ind = gen.nextInt(n-i)+i;
                long temp = a[ind];
                a[ind] = a[i];
                a[i] = temp;
            }
            return a;
        }
        
        public static void swap(int a, int b){
            int temp = a;
            a = b;
            b = temp;
        }
        
        public static HashSet<Integer> primeFactorization(int n)
        {
            HashSet<Integer> a =new HashSet<Integer>();
            for(int i=2;i*i<=n;i++)
            {
                while(n%i==0)
                {
                    a.add(i);
                    n/=i;
                }
            }
            if(n!=1)
                a.add(n);
            return a;
        }
        
        public static void sieve(boolean[] isPrime,int n)
        {
            for(int i=1;i<n;i++)
                isPrime[i] = true;
            
            isPrime[0] = false;
            isPrime[1] = false;
            
            for(int i=2;i*i<n;i++)
            {
                if(isPrime[i] == true)
                {
                    for(int j=(2*i);j<n;j+=i)
                        isPrime[j] = false;
                }
            }
        }
        
        public static int GCD(int a,int b)
        {
            if(b==0)
                return a;
            else
                return GCD(b,a%b);
        }
        
        static class pair implements Comparable<pair>
        {
            Integer x,id;
            Long y;
            pair(int id,int x,long y)
            {
                this.x=x;
                this.y=y;
                this.id=id;
            }
            
           
          


			public int compareTo(pair o) {
                int result = x.compareTo(o.x);
                if(result==0)
                    result = y.compareTo(o.y);
                
                return result;
            }  
            
            public String toString()
            {
                return x+" "+y;
            }
            
            public boolean equals(Object o)
            {
                if (o instanceof pair)
                {
                    pair p = (pair)o;
                    return p.x == x && p.y == y ;
                }
                return false;
            }
            
            public int hashCode()
            {
                return new Long(x).hashCode()*31 + new Long(y).hashCode();
            }
        }
        
    
}

class dsu{
	int parent[];
	dsu(int n){
		parent=new int[n+1];
		for(int i=0;i<=n;i++)
		{
			parent[i]=i;
		}
	}
	int root(int n) {
		while(parent[n]!=n)
		{ 
			parent[n]=parent[parent[n]];
			n=parent[n];
		}
		return n;
	}
	void union(int _a,int _b) {
		int p_a=root(_a);
		int p_b=root(_b);
		
			parent[p_a]=p_b;
		
			
	}
	boolean find(int a,int b) {
		if(root(a)==root(b))
			return true;
		else
			return  false;
	}
	
	
}
class Segment{ 
	int seg[]; 
	int a[];
	int lazy[];
    Segment (int n,int b[]){
		seg=new int[4*n];
		lazy=new int[4*n];
		a=new int[b.length];
		a=b.clone();
	}
    public void build(int node,int start,int end) {
    	if(start==end) {
    		seg[node]=a[start];
    		return ;
    	}
    	int mid=(start+end)/2;
    	build(2*node+1,start,mid);
    	build(2*node+2,mid+1,end);
    	seg[node]=seg[2*node+1]+seg[2*node+2];
    }
    public void update(int node,int start,int end,int id,int val) {
    	if(start==end) {
    		seg[node]=a[start]=val;
    		return;
    	}
    	int mid=(start+end)/2;
    	if(id>=start && id<=mid) {
    		update(2*node+1,start,mid,id,val);
    	}
    	else
    		update(2*node+2,mid+1,end,id,val);
    	seg[node]=seg[2*node+1]+seg[2*node+2];
    }
    public int query(int node,int start,int end,int l,int r) {
    	if(l>end || r<start)
    		return 0;
    	if(start>=l && end<=r)
    		return seg[node];
    	
    	int  mid=(start+end)/2;
    	return (query(2*node+1,start,mid,l,r)+query(2*node+2,mid+1,end,l,r));
    }
    public void updateRange(int node,int start,int end,int l,int r,int val) {
    	if(lazy[node]!=0) {
    		if(start!=end) {
    			lazy[2*node+1]+=lazy[node];
    			lazy[2*node+2]+=lazy[node];
    		}
    		lazy[node]=0;
    	}
    	if(l>end || r<start)
    		return ;
    	if(start>=l && end<=r) {
    		seg[node]=(end-start+1)*val;
    		if(start!=end) {
    			lazy[2*node+1]+=val;
    			lazy[2*node+2]+=val;
    		}
    		lazy[node]=0;
    		return ;
    	}
    	int mid=(start+end)/2;
    	updateRange(2*node+1,start,mid,l,r,val);
    	updateRange(2*node+2,mid+1,end,l,r,val);
    	seg[node]=seg[2*node+1]+seg[2*node+2];
    }
    public int queryRange(int node,int start,int end,int l,int r) {
    	if(l>end || r<start)
    		return 0;
    	if(lazy[node]!=0) {
    		seg[node]=(end-start+1)*lazy[node];
    		if(start!=end) {
    			lazy[2*node+1]+=lazy[node];
    			lazy[2*node+2]+=lazy[node];
    		}
    		lazy[node]=0;
    	}
    	if(start>=l && end<=r)
    		return seg[node];
    	
    	int  mid=(start+end)/2;
    	return (query(2*node+1,start,mid,l,r)+query(2*node+2,mid+1,end,l,r));
    }
    
}