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

Difficulty: HARD
Tags: Complete search

Sorting

Greedy algorithms
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
from sys import stdin
inFile = stdin
tokens = []
tokens_next = 0

def next_str():
	global tokens, tokens_next
	while tokens_next >= len(tokens):
		tokens = inFile.readline().split()
		tokens_next = 0
	tokens_next += 1
	return tokens[tokens_next - 1]

def nextInt():
	return int(next_str())
n = nextInt()
intervals = [(nextInt(), nextInt(), i) for i in range(n)]
intervals.sort(key=lambda x: (x[1], x[0]))
seen = set()
for i in range(n):
	cur = intervals[i][0]
	while cur in seen:
		cur += 1
	seen.add(cur)
	intervals[i] = (intervals[i][0], intervals[i][1], intervals[i][2], cur)
intervals.sort(key=lambda x: x[2])
for i in range(n):
	print(intervals[i][3], end=' ')
print()


n = int(input())
intervals = [list(map(int, input().split())) for i in range(n)]
intervals = list(enumerate(intervals))
intervals.sort(key=lambda x: (x[1][1], x[1][0]))
ans = [0] * n
vis = set()
for (idx, (l, _)) in intervals:
	while l in vis:
		l += 1
	vis.add(l)
	ans[idx] = l
print(' '.join(list(map(str, ans))))


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	n = int(input())
	a = [[list(map(int, input().split())), i] for i in range(n)]
	a.sort()
	now = 1
	avail = [1 for i in range(int(10000000.0 + 1) + 1)]
	ans = [-1 for i in range(n)]
	for k in range(n):
		i = a[k]
		for j in range(i[0][0], i[0][1] + 1):
			if avail[j]:
				avail[j] = 0
				ans[i[1]] = j
				break
		for t in range(k + 1, n):
			if a[t][0][0] == a[k][0][0]:
				a[t][0][0] += 1
			else:
				break
		a.sort()
	print(*ans)
	return
main()


n = int(input())
seg = []
for i in range(n):
	(l, r) = map(int, input().split())
	seg.append((l, r, i))
seg.sort(key=lambda tup: (tup[1], tup[0], tup[2]))
assigned = set()
ans = [0] * n
for i in range(n):
	for j in range(seg[i][0], seg[i][1] + 1, 1):
		if j not in assigned:
			ans[seg[i][2]] = j
			assigned.add(j)
			break
for i in range(n):
	print(ans[i], end=' ')


import random

class Event:

	def __init__(self, id, start, end):
		self.start = start
		self.end = end
		self.id = id
		self.pick = None

	def key(self):
		return (self.start, self.end)
n = int(input())
events = [Event(i, *map(int, input().split())) for i in range(n)]
limit = events[0].end
for event in events:
	limit = max(limit, event.end)
current_events = set()
for i in range(n):
	if len(current_events) == 0:
		pos = limit + 1
		for event in events:
			if event.pick == None and event.start < pos:
				pos = event.start
	for event in events:
		if event.pick == None and event.start == pos:
			current_events.add(event)
	best_event = random.sample(current_events, 1)[0]
	for event in current_events:
		if event.end < best_event.end:
			best_event = event
	best_event.pick = pos
	current_events.remove(best_event)
	pos += 1
result = [events[i].pick for i in range(n)]
print(' '.join(map(str, result)))


n = int(input())
arr = [0] * 10000001
ans = [0] * 100
print()
a2 = []
for i in range(n):
	(l, r) = map(int, input().split())
	tmp = (r, l, i)
	a2.append(tmp)
a2.sort()
for i in range(n):
	m = a2[i]
	r = m[0]
	l = m[1]
	v = m[2]
	dif = r - l + 1
	for j in range(dif):
		if arr[l + j] == 0:
			arr[l + j] = 1
			ans[v] = l + j
			break
for x in range(n):
	print(ans[x], ' ', end='')


n = int(input())
freq = [0] * 10000001
ans = [0] * 100
a = []
for i in range(n):
	(l, r) = map(int, input().split())
	temp = (r, l, i)
	a.append(temp)
a.sort()
for i in range(n):
	(r, l, v) = (a[i][0], a[i][1], a[i][2])
	for j in range(l, r + 1):
		if freq[j] == 0:
			freq[j] = 1
			ans[v] = j
			break
for i in range(n):
	print(ans[i], ' ', end='')


n = int(input())
(a, ans, b) = ([], [0] * n, [0] * 10000001)
for i in range(n):
	(L, R) = map(int, input().split())
	a.append([R, L, i])
a.sort()
for z in a:
	(R, L, i) = z
	for j in range(L, R + 1):
		if b[j] == 0:
			b[j] = 1
			ans[i] = j
			break
print(*ans)