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.io.*;
import java.lang.reflect.Array;
import java.security.cert.TrustAnchor;
import java.util.*;

/**
 * Created by noureldin on 2/20/17.
 */

public class main {


    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        int n = io.getNextInt();
        Integer [] ans = new Integer[n];
        Interval [] I = new Interval[n];
        for (int i = 0;i < n;i++)
            I[i] = new Interval(io.getNextInt(),io.getNextInt());

        boolean [] done = new boolean[n];
        int lst = 0x3f3f3f3f;
        for (int i = 0;i < n;i++){
            int new_max = 0;
            for (int j = 0;j < n;j++)
                if (!done[j])
                    new_max = Math.max(new_max,I[j].r);
            int val = Math.min(new_max,lst - 1),mn = 0x3f3f3f3f,idx = 0;
            for (int j = 0;j < n;j++)
                if (!done[j] && I[j].l <= val && val <= I[j].r){
                    int len = val - I[j].l;
                    if(len < mn){
                        mn = len;
                        idx = j;
                    }
                }
            ans[idx] = val;
            done[idx] = true;
            lst = val;
        }
        for (int i = 0;i < n;i++) io.print(ans[i] + " ");
        io.close();
    }
}

class Interval{
    int l,r;
    public Interval(int l,int r){
        this.l = l;
        this.r = r;
    }
}



class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
}