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.awt.Point;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.io.*;
import java.math.BigInteger;
import static java.math.BigInteger.*;
import java.util.*;

import javax.print.attribute.standard.MediaSize.Other;
public class D{
	
	void solve()throws Exception
	{
		int n=nextInt();
		int[]l=new int[n];
		int[]r=new int[n];
		for(int i=0;i<n;i++)
		{
			l[i]=nextInt();
			r[i]=nextInt();
			if(r[i]-l[i]>n)
			{
				l[i]=r[i]-n;
			}
		}
		int[]res=new int[n];
		HashSet<Integer>h=new HashSet<Integer>();
		for(int i=0;i<n;i++)
			for(int x=l[i];x<=r[i];x++)
				h.add(x);
		int[]x=new int[h.size()];
		int ind=0;
		for(int y: h)
			x[ind++]=y;
		boolean[][]g=new boolean[n][ind];
		for(int i=0;i<n;i++)
			for(int j=0;j<x.length;j++)
				if(x[j]>=l[i] && x[j]<=r[i])
					g[i][j]=true;
		int[]match=new int[ind];
		Arrays.fill(match, -1);
		for(int i=0;i<n;i++)
		{
			if(dfs(i,new boolean[n],g,ind,match))
			{
				
			}
			else
				throw new RuntimeException();
		}
		for(int i=0;i<x.length;i++)
			if(match[i]!=-1)
				res[match[i]]=x[i];
		for(int i=0;i<n;i++)
		{
			if(i==n-1)
				System.out.println(res[i]);
			else
				System.out.print(res[i]+ " " );
		}
	}	
	private boolean dfs(int at, boolean[] vis, boolean[][] g, int m, int[] match) {
		if(at==-1)
			return true;
		if(vis[at])
			return false;
		vis[at]=true;
		for(int i=0;i<m;i++)
			if(g[at][i] && dfs(match[i], vis, g, m, match))
			{
				match[i]=at;
				return true;
			}
		return false;
	}
	private boolean intersect(int x1, int x2, int y1, int y2) {
		if(y2<x1 || x2<y1)
			return false;
		return true;
	}
	BufferedReader reader;
	PrintWriter writer;
	StringTokenizer stk;
	void run()throws Exception
	{
		reader=new BufferedReader(new InputStreamReader(System.in));
		stk=null;
		writer=new PrintWriter(System.out);
		solve();
		reader.close();
		writer.close();
	}
	int nextInt()throws Exception
	{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws Exception
	{	
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws Exception
	{		
		return Double.parseDouble(nextToken());
	}
	String nextString()throws Exception
	{
		return nextToken();
	}
	String nextLine()throws Exception
	{
		return reader.readLine();
	}
	String nextToken()throws Exception
	{
		if(stk==null || !stk.hasMoreTokens())
		{
			stk=new StringTokenizer(nextLine());
			return nextToken();
		}
		return stk.nextToken();
	}
	
	public static void main(String[]a) throws Exception
	{	
		new D().run();

	}
	
}