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:
//package first;//提交代码时，此行要注释掉
import java.math.BigDecimal;//小数
import java.math.BigInteger;//整数
import java.util.*;
public class Main{
	static int N =120;
	static int l[] =new int[N],r[] =new int[N],ans[] =new int[N],vis[] =new int[N];
	public static void main(String args[]) {
		Scanner cin = new Scanner(System.in);
		int n;
		n = cin.nextInt();
		for(int i = 1;i<= n;i++) {
			l[i] =cin.nextInt();
			r[i] =cin.nextInt();
		}
		l[0] = r[0] =0x3f3f3f3f;
		for(int i = 1;i<= n;i++) {
			int k = 0;
			for(int j = 1;j <= n;j++) 
				if(vis[j]==0&&check(j,k))
					k = j;
				ans[k] =l[k];
				vis[k] = 1;
				int p =ans[k]+1;
				for(int j = 1;j <= n;j++)
					if(l[j]<p) {
						l[j] =p;
					}	
		}
		for(int i = 1;i<=n;i++)
			System.out.print(ans[i]+" ");
		
	}
	public static boolean check(int n,int m) {
		if(l[m]>l[n])
			return true;
		else
			return (l[m]==l[n]&&r[m]>r[n]);
	}
	
		
	
	
}