Harry is a bright student. To prepare thoroughly for exams, he completes all the exercises in his book! Now that the exams are approaching fast, he is doing book exercises day and night. He writes down and keeps updating the remaining number of exercises on the back cover of each book.
Harry has a lot of books messed on the floor. Therefore, he wants to pile up the books that still have some remaining exercises into a single pile. He will grab the books one-by-one and add the books that still have remaining exercises to the top of the pile.
Whenever he wants to do a book exercise, he will pick the book with the minimum number of remaining exercises from the pile. In order to pick the book, he has to remove all the books above it. Therefore, if there are more than one books with the minimum number of remaining exercises, he will take the one which requires the least number of books to remove. The removed books are returned to the messy floor. After he picks the book, he will do all the remaining exercises and trash the book.
Since number of books is rather large, he needs your help to tell him the number of books he must remove, for picking the book with the minimum number of exercises.

Note that more than one book can have the same name.

------ Input ------ 

The first line contains a single integer N denoting the number of actions. Then N lines follow. Each line starts with an integer. If the integer is -1, that means Harry wants to do a book exercise. Otherwise, the integer is number of the remaining exercises in the book he grabs next. This is followed by a string denoting the name of the book.

------ Output ------ 

For each -1 in the input, output a single line containing the number of books Harry must remove, followed by the name of the book that Harry must pick.

------ Constraints ------ 

1 < N ≤ 1,000,000
0 ≤ (the number of remaining exercises of each book) < 100,000
The name of each book consists of between 1 and 15 characters 'a' - 'z'.
Whenever he wants to do a book exercise, there is at least one book in the pile.

----- Sample Input 1 ------ 
6
9 english
6 mathematics
8 geography
-1
3 graphics
-1
----- Sample Output 1 ------ 
1 mathematics
0 graphics
----- explanation 1 ------ 
- For the first $-1$: Currently, there are $3$ books in the pile. The book with minimum exercises left amongst these is mathematics. Harry has to remove $1$ book from the top to pick mathematics book and solve the remaining exercises.

- For the second $-1$: The book on the top has the least number of remaining exercises. Thus, Harry has to remove $0$ books from the top pick up graphics book.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
stack = []
for _ in range(int(input())):
	b = input()
	if b == '-1':
		(num, book, count) = stack.pop()
		print(str(count) + ' ' + book)
	else:
		b = b.split()
		num = int(b[0])
		book = b[1]
		if num != 0:
			if len(stack) == 0:
				stack.append([num, book, 0])
			elif num > stack[-1][0]:
				stack[-1][2] += 1
			else:
				stack.append([num, book, 0])


stack = []

def solve():
	N = int(input())
	for _ in range(N):
		inp = input().split()
		inp[0] = int(inp[0])
		if inp[0] == -1:
			print(stack[-1][2], stack[-1][1])
			stack.pop()
		else:
			if inp[0] == 0:
				continue
			if len(stack) == 0 or stack[-1][0] >= inp[0]:
				stack.append([inp[0], inp[1], 0])
			else:
				stack[-1][2] += 1
solve()


n = int(input())
names = []
rest = []
pref = []
size = 0
for tc in range(n):
	r_b = input().split()
	if len(r_b) == 1:
		t = pref[size - 1]
		prev = size - 1
		ind = size - 1
		while rest[ind] != t:
			rest.pop()
			names.pop()
			pref.pop()
			ind -= 1
			size -= 1
		name = names[ind]
		cnt = prev - ind
		rest.pop()
		names.pop()
		pref.pop()
		size -= 1
		print(str(cnt) + ' ' + name)
	else:
		r = int(r_b[0])
		b = r_b[1]
		if r == 0:
			continue
		names.append(b)
		rest.append(r)
		if size == 0:
			pref.append(r)
		else:
			pref.append(min(pref[size - 1], r))
		size += 1


n = int(input())
st = []
for _ in range(n):
	l = input()
	if l == '-1':
		if len(st) > 0:
			a = st.pop()
			print(a[2], a[1])
	else:
		b = l.split()[0]
		if int(b) == 0:
			continue
		if len(st) > 0:
			m = int(st[-1][0])
			if int(b) > m:
				st[-1][2] += 1
			else:
				st.append([b, l.split()[1], 0])
		else:
			st.append([b, l.split()[1], 0])


def li():
	return list(map(int, input().split()))
	return a

def si():
	return input().split()

def ii():
	return int(input())
mins = []
for tastcas in range(int(input())):
	x = si()
	if x[0] == '-1':
		(throw, name, rem) = mins.pop()
		print(throw, name)
	else:
		rem = int(x[0])
		name = x[1]
		if rem != 0:
			k = [0, name, rem]
			try:
				if rem > mins[-1][2]:
					mins[-1][0] += 1
				else:
					mins.append(k)
			except:
				mins.append(k)


lst = []
for _ in range(int(input())):
	inp = list(input().split())
	inp[0] = int(inp[0])
	if inp[0] == 0:
		continue
	if inp[0] > -1:
		if len(lst) == 0:
			lst.append((inp[0], inp[1], 0))
		elif inp[0] > lst[-1][0]:
			lst[-1] = (lst[-1][0], lst[-1][1], lst[-1][2] + 1)
		else:
			lst.append((inp[0], inp[1], 0))
	else:
		subject = lst.pop()
		print(*[subject[2], subject[1]])


stackin = []
stackout = []
top = -1
for _ in range(int(input().strip())):
	inpt = input().strip()
	if inpt != '-1':
		(remques, bookname) = inpt.split()
		remques = int(remques)
		if remques != 0:
			if top > -1:
				if remques > stackin[-1][0]:
					stackout[top] += 1
				else:
					stackin.append([remques, bookname])
					stackout.append(0)
					top += 1
			else:
				stackin.append([remques, bookname])
				stackout.append(0)
				top += 1
	else:
		print(stackout.pop(), stackin.pop()[1])
		top -= 1


stack = []
for _ in range(int(input())):
	q = input().split()
	q[0] = int(q[0])
	if len(q) == 1:
		print(stack[-1][2], stack[-1][1])
		stack.pop()
	elif q[0] == 0:
		continue
	elif len(stack) == 0 or stack[-1][0] >= q[0]:
		stack.append([q[0], q[1], 0])
	else:
		stack[-1][2] += 1


n = int(input())
stack = []
for _ in range(n):
	inp = input().split()
	inp[0] = int(inp[0])
	if inp[0] == -1:
		print(stack[-1][2], stack[-1][1])
		stack.pop()
	else:
		if inp[0] == 0:
			continue
		if len(stack) == 0 or stack[-1][0] >= inp[0]:
			stack.append([inp[0], inp[1], 0])
		else:
			stack[-1][2] += 1


lst = []
mini = []
for _ in range(int(input())):
	k = input()
	if k != '-1':
		k = k.split()
		k[0] = int(k[0])
		if k[0] != 0:
			try:
				if k[0] < mini[-1]:
					mini.append(k[0])
				else:
					mini.append(mini[-1])
			except:
				mini.append(k[0])
			lst.append(k)
	else:
		x = 0
		while lst[-1][0] != mini[-1]:
			lst.pop()
			mini.pop()
			x += 1
		print(f'{x} {lst[-1][1]}')
		lst.pop()
		mini.pop()


t = int(input())
stack = []
min_stack = []
while t:
	arr = list(input().split())
	if int(arr[0]) == -1:
		minimum = min_stack[len(min_stack) - 1]
		count = 0
		while len(stack) > 0 and stack[len(stack) - 1][0] != minimum:
			x = stack.pop()
			count += 1
		print(count, stack[len(stack) - 1][1])
		stack.pop()
		min_stack.pop()
	elif int(arr[0]) > 0:
		if len(min_stack) == 0:
			min_stack.append(int(arr[0]))
		elif min_stack[len(min_stack) - 1] >= int(arr[0]):
			min_stack.append(int(arr[0]))
		stack.append((int(arr[0]), arr[1]))
	t -= 1


l = []
for t in range(int(input())):
	s = input().split()
	if s[0] != '-1':
		p = int(s[0])
		b = s[1]
		if p != 0:
			k = [0, b, p]
			if len(l) == 0:
				l.append(k)
			elif p > l[-1][2]:
				l[-1][0] += 1
			else:
				l.append(k)
	else:
		(c, b, p) = l.pop()
		print(c, b)


stack = []
for _ in range(int(input())):
	inp = input()
	if inp == '-1':
		(ex, book, leading) = stack.pop()
		print(str(leading) + ' ' + book)
	else:
		List = inp.split()
		(ex, book) = (int(List[0]), List[1])
		if ex != 0:
			if len(stack) == 0:
				stack.append([ex, book, 0])
			elif ex > stack[-1][0]:
				stack[-1][2] += 1
			else:
				stack.append([ex, book, 0])


try:
	n = int(input())
	stack = []
	for _ in range(n):
		inp = list(input().split())
		if len(inp) == 1:
			print(stack[-1][2], stack[-1][1])
			stack.pop()
		else:
			subject = inp[1]
			exe_cnt = int(inp[0])
			if exe_cnt > 0:
				if len(stack) == 0:
					stack.append((exe_cnt, subject, 0))
				elif stack[-1][0] >= exe_cnt:
					stack.append((exe_cnt, subject, 0))
				else:
					subject = stack[-1][1]
					exe_cnt = stack[-1][0]
					top = stack[-1][2]
					stack.pop()
					stack.append((exe_cnt, subject, top + 1))
except:
	pass


n = int(input())
arr = []
minArr = []
for _ in range(n):
	a = input().strip()
	if a == '-1':
		x = 0
		while arr[-1][0] != minArr[-1]:
			arr.pop()
			minArr.pop()
			x += 1
		print(f'{x} {arr[-1][1]}')
		arr.pop()
		minArr.pop()
	else:
		(i, s) = a.split()
		i = int(i)
		if i != 0:
			try:
				if i < minArr[-1]:
					minArr.append(i)
				else:
					minArr.append(minArr[-1])
			except:
				minArr.append(i)
			arr.append([i, s])


from collections import deque as dq
n = int(input())
books = []
record = dq([])
while n > 0:
	n -= 1
	line = str(input()).split(' ')
	k = int(line[0])
	if k == -1:
		print(str(record[0]['diff']) + ' ' + str(books.pop()))
		record.popleft()
	elif k > 0:
		name = line[1]
		if len(record) == 0 or k <= record[0]['ex_count']:
			record.appendleft({'ex_count': k, 'diff': 0})
			books.append(name)
		else:
			record[0]['diff'] += 1


N = int(input())
stack = []
for n in range(N):
	line = input().strip().split()
	if int(line[0]) == -1:
		if len(stack) != 0:
			[problems, books, name] = stack.pop()
			print(books, name)
	else:
		problems = int(line[0])
		if problems == 0:
			continue
		if len(stack) != 0 and problems > stack[-1][0]:
			stack[-1][1] += 1
		else:
			stack.append([problems, 0, line[1]])


n = int(input())
books = []
exers = []
exvals = set()
excount = {}
for _ in range(n):
	s = tuple(map(str, input().split()))
	if s[0] == '-1':
		minex = min(exvals)
		rem = 0
		bn = books.pop()
		ev = exers.pop()
		excount[ev] -= 1
		if excount[ev] == 0:
			exvals.remove(ev)
		while ev != minex:
			bn = books.pop()
			ev = exers.pop()
			excount[ev] -= 1
			if excount[ev] == 0:
				exvals.remove(ev)
			rem += 1
		print('{} {}'.format(rem, bn))
	elif int(s[0]) != 0:
		books.append(s[1])
		exers.append(int(s[0]))
		exvals.add(int(s[0]))
		if int(s[0]) in excount:
			excount[int(s[0])] += 1
		else:
			excount[int(s[0])] = 1


n = int(input())
stack = []
for _ in range(n):
	inp = input()
	if inp == '-1':
		print(stack[-1][2], stack[-1][1])
		stack.pop()
	else:
		(ex__no, book_name) = inp.split()
		if ex__no == '0':
			continue
		if len(stack) == 0:
			stack.append([int(ex__no), book_name, 0])
		elif stack[-1][0] >= int(ex__no):
			stack.append([int(ex__no), book_name, 0])
		else:
			stack[-1][2] += 1


N = int(input())
stack = []
for _ in range(N):
	l = input()
	if l == '-1':
		if len(stack) > 0:
			a = stack.pop()
			print(a[2], a[1])
	else:
		b = l.split()[0]
		if int(b) == 0:
			continue
		if len(stack) > 0:
			m = int(stack[-1][0])
			if int(b) > m:
				stack[-1][2] += 1
			else:
				stack.append([b, l.split()[1], 0])
		else:
			stack.append([b, l.split()[1], 0])


arr = []
for n in range(int(input())):
	inputarr = [str(x) for x in input().split()]
	a = int(inputarr[0])
	if a == 0:
		continue
	elif a != -1:
		name = inputarr[1]
		if len(arr) == 0:
			arr.append([a, name, 0])
		elif arr[-1][0] >= a:
			arr.append([a, name, 0])
		else:
			arr[-1][2] += 1
	else:
		print(arr[-1][2], arr[-1][1])
		arr.pop()