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.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.TreeSet;


public class A {
	public static void main(String[] args) throws Exception {
		MScanner sc = new MScanner();
		PrintWriter out = new PrintWriter(System.out);
		int N = sc.nextInt();
		int[] S = new int[N];
		int[] E = new int[N];
		
		TreeSet<Integer> TS = new TreeSet<Integer>();
		for(int a=0;a<N;a++){
			S[a]=sc.nextInt();
			E[a]=sc.nextInt();
			TS.add(S[a]);
		}
		while(!TS.isEmpty()){
			int cur =TS.first();
			int shouldChange = 0;
			int minMax = Integer.MAX_VALUE;
			for(int a=0;a<N;a++)
				if(cur==S[a]){
					if(minMax>E[a]){
						minMax=E[a];
						shouldChange = a;
					}
				}
			for(int a=0;a<N;a++){
				if(a==shouldChange)continue;
				if(cur==S[a]){
					S[a]++;
					TS.add(S[a]);
				}
			}
			TS.remove(cur);
		}

		for(int a=0;a<N;a++)out.print(S[a]+" ");
		out.close();
	}
			



	static class MScanner{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		
		public MScanner() throws Exception{
			stream = System.in;

		}
		int read(){
			if(numChars==-1)
				throw new InputMismatchException();
			if(curChar>=numChars){
				curChar = 0;
				try{
					numChars = stream.read(buf);
				} catch (IOException e){
					throw new InputMismatchException();
				}
				if(numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		
		boolean isSpaceChar(int c){
			return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
		}
		boolean isEndline(int c){
			return c=='\n'||c=='\r'||c==-1;
		}
		int nextInt(){
			return Integer.parseInt(next());
		}
		int[] nextInt(int N){
			int[] ret = new int[N];
			for(int a=0;a<N;a++)
				ret[a] = nextInt();
			return ret;
		}
		int[][] nextInt(int N, int M){
			int[][] ret = new int[N][M];
			for(int a=0;a<N;a++)
				ret[a] = nextInt(M);
			return ret;
		}
		long nextLong(){
			return Long.parseLong(next());
		}
		long[] nextLong(int N){
			long[] ret = new long[N];
			for(int a=0;a<N;a++)
				ret[a] = nextLong();
			return ret;
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		double[] nextDouble(int N){
			double[] ret = new double[N];
			for(int a=0;a<N;a++)
				ret[a] = nextDouble();
			return ret;
		}
		String next(){
			int c = read();
			while(isSpaceChar(c))
				c=read();
			StringBuilder res = new StringBuilder();
			do{
				res.appendCodePoint(c);
				c=read();
			} while(!isSpaceChar(c));
			return res.toString();
		}
		String[] next(int N){
			String[] ret = new String[N];
			for(int a=0;a<N;a++)
				ret[a] = next();
			return ret;
		}
		String nextLine(){
			int c = read();
			while(isEndline(c))
				c=read();
			StringBuilder res = new StringBuilder();
			do{
				res.appendCodePoint(c);
				c = read();
			}while(!isEndline(c));
			return res.toString();
		}
		String[] nextLine(int N){
			String[] ret = new String[N];
			for(int a=0;a<N;a++)
				ret[a] = nextLine();
			return ret;
		}
		
	}
}