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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.util.AbstractCollection;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		PandaScanner in = new PandaScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		D solver = new D();
		solver.solve(1, in, out);
		out.close();
	}
}

class D {
    public void solve(int testNumber, PandaScanner in, PrintWriter out) {
        int n = in.nextInt();
        Interval[] intervals = new Interval[n];
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            intervals[i] = new Interval(i, in.nextInt(), in.nextInt());
        }
        int min = 0;
        Arrays.sort(intervals, Interval.byL);
        PriorityQueue<Interval> q = new PriorityQueue<>(n << 1, Interval.byR);
        int currIdx = 0;
        for (int i = 0; i < n; i++) {
            while (q.isEmpty() || (currIdx < n && intervals[currIdx].l <= min)) {
                q.add(intervals[currIdx]);
                min = intervals[currIdx].l;
                currIdx++;
            }
            Interval currInterval = q.poll();
//            System.out.println(currInterval.l + " " + currInterval.r + " " + min);
            res[currInterval.idx] = Math.max(min, currInterval.l);
            min = res[currInterval.idx] + 1;
        }
        out.println(ArrayUtil.toString(res));
    }
}

class Interval {
    int idx;
    int l;
    int r;
    public Interval(int idx, int l, int r) {
        this.idx = idx;
        this.l = l;
        this.r = r;
    }
    public static Comparator<Interval> byL = new Comparator<Interval>() {
        public int compare(Interval a, Interval b) {
            if (a.l != b.l) {
                return a.l - b.l;
            }
            return a.r - b.r;
        }
    };
    public static Comparator<Interval> byR = new Comparator<Interval>() {
        public int compare(Interval a, Interval b) {
            if (a.r != b.r) {
                return a.r - b.r;
            }
            return a.l - b.l;
        }
    };
}

class PandaScanner {
    public BufferedReader br;
    public StringTokenizer st;
    public InputStream in;

    public PandaScanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(this.in = in));
    }

    public String nextLine() {
        try {
            return br.readLine();
        }
        catch (Exception e) {
            return null;
        }
    }

    public String next() {
        if (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(nextLine().trim());
            return next();
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    }

class ArrayUtil {

    public static<T> String toString(int[] arr) {
        StringBuilder res = new StringBuilder();
        for (int i: arr) {
            res.append(i);
            res.append(' ');
        }
        return res.toString();
    }

    }