The All-Berland National Olympiad in Informatics has just ended! Now Vladimir wants to upload the contest from the Olympiad as a gym to a popular Codehorses website.

Unfortunately, the archive with Olympiad's data is a mess. For example, the files with tests are named arbitrary without any logic.

Vladimir wants to rename the files with tests so that their names are distinct integers starting from 1 without any gaps, namely, "1", "2", ..., "n', where n is the total number of tests.

Some of the files contain tests from statements (examples), while others contain regular tests. It is possible that there are no examples, and it is possible that all tests are examples. Vladimir wants to rename the files so that the examples are the first several tests, all all the next files contain regular tests only.

The only operation Vladimir can perform is the "move" command. Vladimir wants to write a script file, each of the lines in which is "move file_1 file_2", that means that the file "file_1" is to be renamed to "file_2". If there is a file "file_2" at the moment of this line being run, then this file is to be rewritten. After the line "move file_1 file_2" the file "file_1" doesn't exist, but there is a file "file_2" with content equal to the content of "file_1" before the "move" command.

Help Vladimir to write the script file with the minimum possible number of lines so that after this script is run:

  * all examples are the first several tests having filenames "1", "2", ..., "e", where e is the total number of examples; 
  * all other files contain regular tests with filenames "e + 1", "e + 2", ..., "n", where n is the total number of all tests. 

Input

The first line contains single integer n (1 ≤ n ≤ 105) — the number of files with tests.

n lines follow, each describing a file with test. Each line has a form of "name_i type_i", where "name_i" is the filename, and "type_i" equals "1", if the i-th file contains an example test, and "0" if it contains a regular test. Filenames of each file are strings of digits and small English letters with length from 1 to 6 characters. The filenames are guaranteed to be distinct.

Output

In the first line print the minimum number of lines in Vladimir's script file.

After that print the script file, each line should be "move file_1 file_2", where "file_1" is an existing at the moment of this line being run filename, and "file_2" — is a string of digits and small English letters with length from 1 to 6.

Examples

Input

5
01 0
2 1
2extra 0
3 1
99 0


Output

4
move 3 1
move 01 5
move 2extra 4
move 99 3


Input

2
1 0
2 1


Output

3
move 1 3
move 2 1
move 3 2

Input

5
1 0
11 1
111 0
1111 1
11111 0


Output

5
move 1 5
move 11 1
move 1111 2
move 111 4
move 11111 3

Difficulty: HARD
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	n = I()
	a = set()
	b = set()
	for _ in range(n):
		(f, t) = LS()
		if t == '0':
			b.add(f)
		else:
			a.add(f)
	al = len(a)
	bl = len(b)
	r = []
	ta = set([str(i) for i in range(1, al + 1)])
	tb = set([str(i) for i in range(al + 1, al + bl + 1)])
	bb = tb & b
	b -= bb
	tb -= bb
	aa = ta & a
	a -= aa
	ta -= aa
	ua = a & tb
	ub = b & ta
	sa = ta - b
	sb = tb - a
	ran = 'iehn00'
	while ua or ub:
		if not sa and (not sb):
			if ua:
				t = ua.pop()
				sb.add(t)
				a.remove(t)
				a.add(ran)
			else:
				t = ub.pop()
				sa.add(t)
				b.remove(t)
				b.add(ran)
			r.append('move {} {}'.format(t, ran))
		if sa:
			t = sa.pop()
			if ua:
				k = ua.pop()
				a.remove(k)
				sb.add(k)
			else:
				k = a.pop()
			ta.remove(t)
			r.append('move {} {}'.format(k, t))
		if sb:
			t = sb.pop()
			if ub:
				k = ub.pop()
				b.remove(k)
				sa.add(k)
			else:
				k = b.pop()
			tb.remove(t)
			r.append('move {} {}'.format(k, t))
	while a:
		k = a.pop()
		t = ta.pop()
		r.append('move {} {}'.format(k, t))
	while b:
		k = b.pop()
		t = tb.pop()
		r.append('move {} {}'.format(k, t))
	return '{}\n'.format(len(r)) + '\n'.join(r)
print(main())


import random

def genTemp():
	sl = ''
	firstTime = True
	while firstTime or sl in pre or sl in post:
		sl = ''
		firstTime = False
		for i in range(6):
			sl += chr(random.randint(ord('a'), ord('z')))
	return sl
n = int(input())
e = 0
pre = set()
post = set()
for i in range(n):
	(name, tp) = input().split()
	if tp == '1':
		e += 1
		pre.add(name)
	else:
		post.add(name)
temp = genTemp()
preAns = {str(x) for x in range(1, e + 1)}
postAns = {str(x) for x in range(e + 1, n + 1)}
preMissing = preAns - pre
postMissing = postAns - post
preToChange = pre - preAns
postToChange = post - postAns
preFree = preMissing - postToChange
postFree = postMissing - preToChange
preWrong = preToChange & postMissing
postWrong = postToChange & preMissing
ans = []
while preToChange or postToChange:
	if not postFree and (not preFree):
		if preToChange:
			x = preToChange.pop()
			preWrong.discard(x)
			ans.append(('move', x, temp))
			preToChange.add(temp)
			if x in postAns:
				postFree.add(x)
		else:
			x = postToChange.pop()
			ans.append(('move', x, temp))
			postWrong.discard(x)
			postToChange.add(temp)
			if x in postAns:
				preFree.add(x)
	elif preFree:
		if preWrong:
			x = preWrong.pop()
			preToChange.discard(x)
		else:
			x = preToChange.pop()
		y = preFree.pop()
		ans.append(('move', x, y))
		preMissing.discard(y)
		if x in postAns:
			postFree.add(x)
	else:
		if postWrong:
			x = postWrong.pop()
			postToChange.discard(x)
		else:
			x = postToChange.pop()
		y = postFree.pop()
		ans.append(('move', x, y))
		postMissing.discard(y)
		if x in preAns:
			preFree.add(x)
print(len(ans))
for tup in ans:
	print(*tup)


def print_all():
	print(top)
	print(free_top)
	print(busy_top)
	print(bottom)
	print(free_bottom)
	print(busy_bottom)
n = int(input())
top = set()
bottom = set()
for i in range(n):
	(name, type) = input().split()
	if type == '1':
		top.add(name)
	else:
		bottom.add(name)
top_order = set((str(i) for i in range(1, len(top) + 1)))
bottom_order = set((str(i) for i in range(len(top) + 1, len(bottom) + len(top) + 1)))
q = top_order & top
top_order -= q
top -= q
q = bottom_order & bottom
bottom_order -= q
bottom -= q
busy_top = top_order & bottom
free_top = top_order - bottom
busy_bottom = bottom_order & top
free_bottom = bottom_order - top
if len(top_order) + len(bottom_order) == 0:
	print(0)
	exit(0)
if len(free_bottom) + len(free_top) == 0:
	(x, y) = (busy_top.pop(), 'rft330')
	free_top.add(x)
	bottom.remove(x)
	bottom.add(y)
	print(len(top_order) + len(bottom_order) + 1)
	print('move', x, y)
else:
	print(len(top_order) + len(bottom_order))
cross_block = min(len(busy_bottom), len(busy_top))
if len(free_top) > 0 and cross_block > 0:
	x = free_top.pop()
	for i in range(cross_block):
		(x, y) = (busy_bottom.pop(), x)
		top.remove(x)
		print('move', x, y)
		(x, y) = (busy_top.pop(), x)
		bottom.remove(x)
		print('move', x, y)
	free_top.add(x)
cross_block = min(len(busy_bottom), len(busy_top))
if len(free_bottom) > 0 and cross_block > 0:
	x = free_bottom.pop()
	for i in range(cross_block):
		(x, y) = (busy_top.pop(), x)
		bottom.remove(x)
		print('move', x, y)
		(x, y) = (busy_bottom.pop(), x)
		top.remove(x)
		print('move', x, y)
	free_bottom.add(x)
if len(busy_bottom) == 0:
	for i in range(len(bottom)):
		print('move', bottom.pop(), free_bottom.pop())
	free_top |= busy_top
	busy_top.clear()
	for i in range(len(top)):
		print('move', top.pop(), free_top.pop())
elif len(busy_top) == 0:
	for i in range(len(top)):
		print('move', top.pop(), free_top.pop())
	free_bottom |= busy_bottom
	busy_bottom.clear()
	for i in range(len(bottom)):
		print('move', bottom.pop(), free_bottom.pop())


n = int(input())
t = [1] + [0] * n
(b, a) = d = ([], [])
(h, s) = ([], [])
for i in range(n):
	(f, k) = input().split()
	d[int(k)].append(f)
m = len(a)
for i in a:
	if i.isdigit() and i[0] != '0':
		j = int(i)
		if 0 < j <= m:
			t[j] = 1
		elif m < j <= n:
			t[j] = -1
		else:
			s.append(i)
	else:
		s.append(i)
for i in b:
	if i.isdigit() and i[0] != '0':
		j = int(i)
		if m < j <= n:
			t[j] = 1
		elif 0 < j <= m:
			t[j] = -1
		else:
			s.append(i)
	else:
		s.append(i)
x = [j for j in range(1, m + 1) if t[j] < 0]
y = [j for j in range(m + 1, n + 1) if t[j] < 0]
u = [j for j in range(1, m + 1) if not t[j]]
v = [j for j in range(m + 1, n + 1) if not t[j]]
if not s and (x or y):
	s = ['0']
	if y:
		i = y.pop()
		v.append(i)
	else:
		i = x.pop()
		u.append(i)
	h.append(str(i) + ' 0')
	t[i] = 0
while x or y:
	if v and x:
		i = x.pop()
		j = v.pop()
		t[j] = 1
		h.append(str(i) + ' ' + str(j))
		u.append(i)
	else:
		(u, v, x, y) = (v, u, y, x)
k = 1
for j in s:
	while t[k] == 1:
		k += 1
	h.append(j + ' ' + str(k))
	k += 1
d = '\nmove '
print(str(len(h)) + d + d.join(h) if h else 0)