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.io.*;

// Solution

public class Main 
{    
  public static void main (String[] argv) 
  {
	  new Main();
  } 
     
  
  boolean test = false;
  
  int n;

  public Main() {
	  FastReader in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
	  //FastReader in = new FastReader(new BufferedReader(new FileReader("Main.in")));
      
      n = in.nextInt();
      PriorityQueue<Interval> pq = new PriorityQueue<>(n);
      
      for(int i = 0; i < n; ++i){
          int s = in.nextInt();
          int e = in.nextInt();
          pq.offer(new Interval(s, e, i));
      }
      
      
      
      int[] ans = new int[n];
      for(int i = 0; i < n; i++){          
          Interval itv = pq.poll();
          while (!pq.isEmpty() && pq.peek().s <= itv.s) {
              Interval chg = pq.poll();
              chg.s = itv.s + 1;
              pq.offer(chg);
          }          
          ans[itv.i] = itv.s;
      }
      for(int v : ans)
         System.out.print(v + " ");
      System.out.println();
  }
  
  class Interval implements Comparable<Interval>{
      int s, e, i;
      public Interval(int ss,  int ee, int ii) {
          s = ss;
          e = ee;
          i = ii;
      }
      
      @Override
      public int compareTo(Interval o) {
          if (s != o.s) return s - o.s;
          return e - o.e;
      }
  }
     
  private int max(int a, int b) {
      return a >  b ? a : b;
  }
  
  private int min(int a, int b) {
      return a >  b ? b : a;
  }
  
  
  static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader(BufferedReader in)
        {            
            br = in;
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    String line = br.readLine();
                    if (line == null || line.length() == 0) return "";
                    st = new StringTokenizer(line);
                }
                catch (IOException  e)
                {
                    return "";
                    //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)
            {
                return "";
                //e.printStackTrace();
            }
            return str;
        }
    }
}