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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public class Contest {

	static final Random random = new Random();

	static PrintWriter out = new PrintWriter(System.out);

	static class Point implements Comparable<Point> {

		int l, r, index;

		Point(int l, int r, int index) {
			this.l = l;
			this.r = r;
			this.index = index;
		}

		@Override
		public int compareTo(Point o) {
			if(r != o.r)
				return r - o.r;
			return l - o.l;
		}

	}

	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		Point[] a = new Point[n];

		int idx = 0;

		int[] res = new int[n];
		int[] res2 = new int[n];
		boolean[] taken = new boolean[(int) 1e7];
		boolean[] taken2 = new boolean[(int) 1e7];

		for (int i = 0; i < n; i++) {
			Point p = new Point(sc.nextInt() - 1, sc.nextInt() - 1, i);
//			if (p.l == p.r) {
//				taken[p.l] = true;
//				taken2[p.l] = true;
//				res[i] = p.l + 1;
//				res2[i] = p.l + 1;
//			} else {
				a[idx] = p;
				idx++;
//			}
		}

		Arrays.sort(a, 0, n);
		boolean yes = false;
		for (int i = 0; i < idx; i++) {
			int l = a[i].l, r = a[i].r;
			yes = false;
			for (int j = l; j <= r; j++) {
				if (!taken[j]) {
					taken[j] = true;
					res[a[i].index] = j + 1;
					yes = true;
					break;
				}
			}
			if (!yes)
				break;
		}

		if (!yes) {

			for (int i = 0; i < idx; i++) {
				int l = a[i].l, r = a[i].r;
				yes = false;
				for (int j = r; j >= l; j--) {
					if (!taken2[j]) {
						taken2[j] = true;
						res2[a[i].index] = j + 1;
						break;
					}
				}
			}

		}

		for (int i = 0; i < n; i++) {
			out.print((!yes ? res2[i] : res[i]) + " ");
		}
		out.println();

		out.flush();
	}

	static void Arrayssort(int[] a) {
		int n = a.length;// shuffle, then sort
		for (int i = 0; i < n; i++) {
			int oi = random.nextInt(n);
			int temp = a[oi];
			a[oi] = a[i];
			a[i] = temp;
		}
		java.util.Arrays.sort(a);
	}

	private static class Scanner {
		public BufferedReader reader;
		public StringTokenizer st;

		public Scanner(InputStream file) throws FileNotFoundException {
			reader = new BufferedReader(new InputStreamReader(file));
			st = null;
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String line = reader.readLine();
					if (line == null)
						return null;
					st = new StringTokenizer(line);
				} catch (Exception e) {
					throw (new RuntimeException());
				}
			}
			return st.nextToken();
		}

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

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() throws IOException {
			return reader.readLine();
		}
	}

}