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:
// practice with kaiboy
import java.io.*;
import java.util.*;

public class CF45D extends PrintWriter {
	CF45D() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF45D o = new CF45D(); o.main(); o.flush();
	}

	static final int T = 10000000;
	int[] ll, rr;
	int[] pq, iq; int cnt;
	boolean lt(int i, int j) {
		return rr[i] < rr[j];
	}
	int p2(int p) {
		return (p *= 2) > cnt ? 0 : p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p;
	}
	void pq_up(int i) {
		int j, p, q;
		for (p = pq[i]; (q = p / 2) > 0 && lt(i, j = iq[q]); p = q)
			iq[pq[j] = p] = j;
		iq[pq[i] = p] = i;
	}
	void pq_dn(int i) {
		int j, p, q;
		for (p = pq[i]; (q = p2(p)) > 0 && lt(j = iq[q], i); p = q)
			iq[pq[j] = p] = j;
		iq[pq[i] = p] = i;
	}
	void pq_add(int i) {
		pq[i] = ++cnt; pq_up(i);
	}
	int pq_remove_first() {
		int i = iq[1], j = iq[cnt--];
		if (j != i) {
			pq[j] = 1; pq_dn(j);
		}
		pq[i] = 0;
		return i;
	}
	void main() {
		int n = sc.nextInt();
		ll = new int[n]; rr = new int[n]; pq = new int[n]; iq = new int[1 + n];
		Integer[] ii = new Integer[n];
		for (int i = 0; i < n; i++) {
			ll[i] = sc.nextInt();
			rr[i] = sc.nextInt();
			ii[i] = i;
		}
		Arrays.sort(ii, (i, j) -> ll[i] - ll[j]);
		int[] tt = new int[n];
		for (int h = 0, i, t = 1; t <= T; t++) {
			while (h < n && ll[i = ii[h]] == t) {
				pq_add(i);
				h++;
			}
			if (cnt > 0) {
				i = pq_remove_first();
				tt[i] = t;
			} else if (h == n)
				break;
		}
		for (int i = 0; i < n; i++)
			print(tt[i] + " ");
		println();
	}
}