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 Main {

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

		int[] beg = new int[n];
		int[] end = new int[n];
		for (int i = 0; i < n; i++) {
			beg[i] = sc.nextInt();
			end[i] = sc.nextInt();
		}

		int[] ps = new int[2 * n * 3];
		int size = 0;
		for (int i = 0; i < n; i++) {
			ps[size++] = beg[i] - 1;
			ps[size++] = beg[i];
			ps[size++] = beg[i] + 1;
			ps[size++] = end[i] - 1;
			ps[size++] = end[i];
			ps[size++] = end[i] + 1;

		}
		sort(ps);
		ps = unique(ps);

//		tr(ps);

		ArrayList<Integer> c = new ArrayList<Integer>();
		ArrayList<Integer> d = new ArrayList<Integer>();

		for (int i = 0; i + 1 < ps.length; i++) {
			c.add(ps[i] + 1);
			d.add(ps[i+1]);
		}

//		tr(c);
//		tr(d);

		int m = 2 + n + c.size();

		int s = 0;
		int t = 1;
		// left = [2,  2 + n)
		// right = [2 + n, 2 + n + c.size())

		cap = new int[m][m];
		flow = new int[m][m];
		prev = new int[m];

		for (int i = 0; i < n; i++) {
			cap[s][2+i] = 1;
		}
		for (int j = 0; j < c.size(); j++) {
			int w = d.get(j) - c.get(j) + 1;
			cap[2 + n + j][t] = w;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < c.size(); j++) {
				int cj = c.get(j);
				int dj = d.get(j);
				if (beg[i] <= cj && dj <= end[i]) cap[2+i][2+n+j] = 1;
			}
		}

		int f = edmondsKarp(m, s, t);
//		tr(f);
//		tr(prev);

		int[] ans = new int[n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < c.size(); j++) {
				int cj = c.get(j);
				int dj = d.get(j);
				if (flow[2+i][2+n+j] == 1) {
					int v = c.get(j);
					ans[i] = v;
					c.set(j, v+1);
				}
			}
		}

		print(ans);
	}


	final int inf = 987654321;
	int cap[][];
	int flow[][];
	int[] prev;

	int augment(int N, int s, int t, ArrayList<Integer> path) {
		Arrays.fill(prev, -1);
		Queue<Integer> up = new LinkedList<Integer>();
		up.add(s);
		prev[s] = s;
		while (!up.isEmpty()) {
			int cur = up.poll();
			if (cur == t) {
				int bottleneck = inf;
				while (cur != s) {
					path.add(cur);
					bottleneck = Math.min(bottleneck, cap[prev[cur]][cur]
							- flow[prev[cur]][cur]);
					cur = prev[cur];
				}
				path.add(s);
				Collections.reverse(path);
				return bottleneck;
			}
			for (int next = 0; next < N; next++) {
				if (prev[next] == -1 && cap[cur][next] - flow[cur][next] > 0) {
					prev[next] = cur;
					up.add(next);
				}
			}
		}
		return -1;
	}

	int edmondsKarp(int N, int s, int t) {
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) flow[i][j] = 0;
		int max_flow = 0;
		for (;;) {
			ArrayList<Integer> path = new ArrayList<Integer>();
			int bottleneck = augment(N, s, t, path);
			if (bottleneck == -1)
				break;
			for (int i = 0; i + 1 < path.size(); i++) {
				int from = path.get(i), to = path.get(i + 1);
				flow[from][to] += bottleneck;
				flow[to][from] -= bottleneck;
			}
			max_flow += bottleneck;
		}
		return max_flow;
	}

	int[] unique(int[] v) {
		int[] t = v.clone();
		if (v.length <= 1) return t;
		sort(t);
		int p = 1;
		for (int i = 1; i < v.length; i++) {
			if (t[i-1] != t[i]) {
				t[p++] = t[i];
			}
		}
		return Arrays.copyOf(t, p);
	}

	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 Main().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;
		}
	}
}