Problem: On a history lesson the teacher asked Vasya to name the dates when n famous events took place. He doesn't remembers the exact dates but he remembers a segment of days [li, ri] (inclusive) on which the event could have taken place. However Vasya also remembers that there was at most one event in one day. Help him choose such n dates of famous events that will fulfill both conditions. It is guaranteed that it is possible.

Input

The first line contains one integer n (1 ≤ n ≤ 100) — the number of known events. Then follow n lines containing two integers li and ri each (1 ≤ li ≤ ri ≤ 107) — the earliest acceptable date and the latest acceptable date of the i-th event.

Output

Print n numbers — the dates on which the events took place. If there are several solutions, print any of them. It is guaranteed that a solution exists.

Examples

Input

3
1 2
2 3
3 4


Output

1 2 3 


Input

2
1 3
1 3


Output

1 2 

Solution (in JAVA):

Solution:
import java.util.*; 
    import java.math.*;
    import java.io.*;
    import java.text.DecimalFormat;
    import java.math.BigInteger;
    public class Main{
        //static int d=20;
        static long mod=1000000007 ;
        static HashMap<String,Double> hm=new HashMap<>(); 
        static ArrayList<ArrayList<Integer>> arr;
        static long[][] color;
        static int[] a;
        static int[] vis,num;
        static double val;
        public static void main(String[] args)  throws IOException {
            boolean online =false;
            String fileName = "C-large-practice";
            PrintWriter out;
            if (online) {
                s.init(new FileInputStream(new File(fileName + ".in")));
                 out= new PrintWriter(new FileWriter(fileName + "out.txt"));
            }
             else {
                s.init(System.in);   
            
                out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
            }
            
            //out.println(ans);
            int n=s.ni();
            int[]  ans=new int[n];
            name[] interval=new name[n];
            for(int i=0;i<n;i++)
                interval[i]=new name(s.ni(),s.ni(),i);
            Arrays.sort(interval);
            int last=0;
            HashSet<Integer> hs=new HashSet<>();
            for(int i=0;i<n;i++){
                for(int j=interval[i].l;j<=interval[i].r;j++){
                    if(!hs.contains(j)){
                        hs.add(j);
                        ans[interval[i].id]=j;
                        break;
                    }
                }
            }
            for(int i=0;i<n;i++)
                out.print(ans[i]+" ");
            out.close();

        }
   
        public static long pow2(long a,long b){
                long ans=1;
                while(b>0){
                    if(b%2==1)
                        ans=(a*ans);
                    a=(a*a);
                    b/=2;
                }
                return  ans;
        }
        public static double pow3(double a,long b){
                double ans=1;
                while(b>0){
                    if(b%2==1)
                        ans=(a*ans);
                    a=(a*a);
                    b/=2;
                }
                return  ans;
        }

         static class name implements Comparable<name> {
            int l,r,id,sz;
            public name(int  x,int y,int z){
                l=x;
                r=y;
                id=z;
                sz=r-l;
            }
            public int compareTo(name o){
               
                    return r-o.r;
            }
        }
        public static class s {
            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 ns() throws IOException {
                while ( ! tokenizer.hasMoreTokens() ) {
                    //TODO add check for eof if necessary
                    tokenizer = new StringTokenizer(
                        reader.readLine() );
                }
                return tokenizer.nextToken();
            }
        
            static int ni() throws IOException {
                return Integer.parseInt( ns() );
            }
        
            static double nd() throws IOException {
                return Double.parseDouble( ns() );
            }
            static long nl() throws IOException {
                return Long.parseLong( ns() );
            }
            
        }
    }