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 static java.util.Arrays.deepToString;
import static java.util.Arrays.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main2 {

	class Tuple implements Comparable<Tuple> {
		int a, b, id;

		public int compareTo(Tuple o) {
			if (b != o.b) return b < o.b ? -1 : 1;
			if (a != o.a) return a < o.a ? -1 : 1;
			return 0;
		}

		public Tuple(int a, int b, int id) {
			this.a = a;
			this.b = b;
			this.id = id;
		}
	}


	void solve() {
		int n = sc.nextInt();

		Tuple[] ts = new Tuple[n];

		int ma = 0;
		for (int i = 0; i < n; i++) {
			ts[i] = new Tuple(sc.nextInt(), sc.nextInt(), i);
			ma = Math.max(ma, ts[i].a);
			ma = Math.max(ma, ts[i].b);
		}
		sort(ts);
		boolean[] done = new boolean[ma + 1];
		int[] ans = new int[n];

		for (int i = 0; i < n; i++) {
			int x;
			for (x = ts[i].a; done[x] == true; x++);
			done[x] = true;
			ans[ts[i].id] = x;
		}
		print(ans);
	}

	void print(int[] a) {
		out.print(a[0]);
		for (int i = 1; i < a.length; i++) out.print(" " + a[i]);
		out.println();
	}

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}
	static void fill(int[][] a, int val) {
		for(int i = 0; i < a.length; i++) Arrays.fill(a[i], val);
	}
	static void fill(int[][][] a, int val) {
		for(int i = 0; i < a.length; i++) fill(a[i], val);
	}

	public static void main(String[] args) throws Exception {
		new Main2().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}