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:
/**
 * Created by IntelliJ IDEA.
 * User: Taras_Brzezinsky
 * Date: 9/13/11
 * Time: 5:33 PM
 * To change this template use File | Settings | File Templates.
 */

import sun.net.ftp.FtpProtocolException;
import sun.util.calendar.JulianCalendar;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.sql.Time;
import java.util.*;

public class TaskA extends Thread {
    public TaskA() {
        this.input = new BufferedReader(new InputStreamReader(System.in));
        this.output = new PrintWriter(System.out);
        this.setPriority(Thread.MAX_PRIORITY);
    }



    static class Event implements Comparable<Event>{
        int left, right, ID;
        public Event(int left, int right, int ID) {
            this.left =  left;
            this.right = right;
            this.ID = ID;
        }
        public int compareTo(Event o) {
            if (this.left == o.left) {
                if (this.right == o.right) {
                    return this.ID - o.ID;
                } else {
                    return this.right - o.right;
                }
            } else {
                return this.left - o.left;
            }
        }
    }

    static class Worker implements Comparable<Worker>{
        int where, ID;
        public Worker(int where, int ID) {
            this.where = where;
            this.ID = ID;
        }

        public int compareTo(TaskA.Worker o) {
            if (this.where == o.where) {
                return this.ID - o.ID;
            } else {
                return this.where - o.where;
            }
        }
    }



    private void solve() throws Throwable {
        int n = nextInt();
        Event events[] = new Event[n];
        for (int i = 0; i < n; ++i) {
            events[i] = new Event(nextInt(), nextInt(), i);
        }
        Arrays.sort(events);
        int last = 0;
        int []finalStandings = new int[n];
        ArrayList<Worker> process = new ArrayList<Worker>();
        for (int i = 0; i < n || !process.isEmpty(); ) {
            if (process.isEmpty()) {
                last = events[i].left;
            }
            while (i < n && events[i].left == last) {
                process.add(new Worker(events[i].right, events[i].ID));
                ++i;
            }
            Collections.sort(process);
            Worker good = process.get(0);
            finalStandings[good.ID] = last++;
            process.remove(0);
        }
        for (int current : finalStandings) {
            output.print(current + " ");
        }

    }

    public void run() {
        try {
            solve();
        } catch (Throwable e) {
            System.err.println(e.getMessage());
            e.printStackTrace();
            System.exit(666);
        } finally {
            output.flush();
            output.close();
        }
    }

    public static void main(String[] args) {
        new TaskA().start();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    private String nextToken() throws IOException {
        while (tokens == null || !tokens.hasMoreTokens()) {
            tokens = new StringTokenizer(input.readLine());
        }
        return tokens.nextToken();
    }

    private BufferedReader input;
    private PrintWriter output;
    private StringTokenizer tokens = null;
}