For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$.
* get($key$): Print the value with the specified $key$. Print 0 if there is no such element.
* delete($key$): Delete the element with the specified $key$.
* dump($L$, $R$): Print all elements formed by a pair of the key and the value such that the key is greater than or equal to $L$ and less than or equal to $R$ in lexicographic order.

Constraints

* $1 \leq q \leq 200,000$
* $1 \leq x \leq 1,000,000,000$
* $1 \leq $ length of $key$ $ \leq 20$
* $key$ consists of lower-case letters
* $L \leq R$ in lexicographic order
* The total number of elements printed by dump operations does not exceed $1,000,000$

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $key$ $x$


or


1 $key$


or


2 $key$


or


3 $L$ $R$


where the first digits 0, 1, 2 and 3 represent insert, get, delete and dump operations.

Output

For each get operation, print the corresponding value.
For each dump operation, print the corresponding elements formed by a pair of the key and the value. For the dump operation, print the elements (a pair of key and value separated by a space character) in ascending order of the keys.

Example

Input

9
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red
3 w z


Output

1
4
0
0
white 5

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
import bisect
n = int(input())
arr = []
lines = sys.stdin.readlines()
ans = [None] * n
d = {}
for i in range(n):
	(q, *arg) = lines[i].split()
	key = arg[0]
	idx = bisect.bisect_left(arr, arg[0])
	if q == '0':
		if idx == len(arr) or arr[idx] != key:
			arr.insert(idx, key)
		d[key] = arg[1]
	elif q == '1':
		ans[i] = d[key] if idx != len(arr) and arr[idx] == key else '0'
	elif q == '2':
		if idx < len(arr) and arr[idx] == key:
			del arr[idx]
			del d[key]
	elif q == '3':
		r_idx = bisect.bisect_right(arr, arg[1])
		ans[i] = '\n'.join([f'{key_} {d[key_]}' for key_ in arr[idx:r_idx]]) if r_idx - idx != 0 else None
[print(x) for x in ans if x is not None]


from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = a[1]
	if a[0] == '0':
		if ki not in dict:
			insort_left(keytbl, ki)
		dict[ki] = int(a[2])
	elif a[0] == '1':
		print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			dict[ki] = 0
	else:
		L = bisect_left(keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			if dict[keytbl[j]] > 0:
				print(keytbl[j], dict[keytbl[j]])


def resolve():
	import sys
	import bisect
	input = sys.stdin.readline
	n = int(input())
	ans = dict()
	need_sort = True
	sorted_keys = None
	for _ in range(n):
		(q, key, *x) = input().split()
		if q == '0':
			if key in ans:
				ans[key] = x[0]
			else:
				ans[key] = x[0]
				need_sort = True
		elif q == '1':
			if key in ans:
				print(ans[key])
			else:
				print(0)
		elif q == '2':
			ans[key] = '0'
		else:
			if sorted_keys is None:
				sorted_keys = sorted(ans.keys())
			if need_sort:
				sorted_keys = sorted(ans.keys())
				need_sort = False
			(l, r) = (key, x[0])
			fr = bisect.bisect_left(sorted_keys, l)
			to = bisect.bisect_right(sorted_keys, r)
			for i in range(fr, to):
				if ans[sorted_keys[i]] != '0':
					print(sorted_keys[i], ans[sorted_keys[i]])
resolve()


from collections import defaultdict
import bisect

def main():
	q = int(input())
	d = defaultdict(int)
	inserted_flag = False
	sorted_keys = None
	for _ in range(q):
		para = input().split()
		if para[0] == '0':
			d[para[1]] = int(para[2])
			inserted_flag = True
		elif para[0] == '1':
			if para[1] in d.keys():
				print(d[para[1]])
			else:
				print('0')
		elif para[0] == '2':
			if para[1] in d.keys():
				del d[para[1]]
				inserted_flag = True
		elif para[0] == '3':
			if sorted_keys is None:
				sorted_keys = sorted(d.keys())
			if inserted_flag:
				sorted_keys = sorted(d.keys())
				inserted_flag = False
			l = bisect.bisect_left(sorted_keys, para[1])
			r = bisect.bisect_right(sorted_keys, para[2])
			for i in range(l, r):
				print('{} {}'.format(sorted_keys[i], d[sorted_keys[i]]))
main()


from bisect import insort, bisect_right, bisect_left

class Range_map:

	def __init__(self):
		self.rm = dict()
		self.lr = []

	def insert(self, x, y):
		if x not in self.rm:
			insort(self.lr, x)
		self.rm[x] = y

	def get(self, x):
		print(self.rm.get(x, 0))

	def delete(self, x):
		if x in self.rm:
			self.rm[x] = 0

	def dump(self, l, r):
		lb = bisect_left(self.lr, l)
		ub = bisect_right(self.lr, r)
		for i in range(lb, ub):
			k = self.lr[i]
			if k in self.rm and self.rm[k] != 0:
				print(f'{k} {self.rm[k]}')
rm = Range_map()
for _ in range(int(input())):
	(op, x, y) = (input() + ' 1').split()[:3]
	if op == '0':
		rm.insert(x, int(y))
	elif op == '1':
		rm.get(x)
	elif op == '2':
		rm.delete(x)
	else:
		rm.dump(x, y)


import bisect
q = int(input())
M = {}
list_key_sorted = []
for _ in range(q):
	(command, *list_num) = input().split()
	if command == '0':
		key = list_num[0]
		x = int(list_num[1])
		if key not in M:
			bisect.insort_left(list_key_sorted, key)
		M[key] = x
	elif command == '1':
		key = list_num[0]
		if key in M:
			if M[key] == None:
				print(0)
			else:
				print(M[key])
		else:
			print(0)
	elif command == '2':
		key = list_num[0]
		if key in M:
			M[key] = None
	elif command == '3':
		L = list_num[0]
		R = list_num[1]
		index_left = bisect.bisect_left(list_key_sorted, L)
		index_right = bisect.bisect_right(list_key_sorted, R)
		for index in range(index_left, index_right):
			key_ans = list_key_sorted[index]
			if M[key_ans] != None:
				print(key_ans, M[key_ans])
	else:
		raise


from bisect import bisect_left, bisect_right, insort_left
from typing import Dict, List
num_query = int(input())
d: Dict[str, int] = {}
keys: List[str] = []
for _ in range(num_query):
	(op, *v) = input().split()
	if '0' == op:
		if v[0] not in d:
			insort_left(keys, v[0])
		d[v[0]] = int(v[1])
	elif '1' == op:
		if v[0] in d:
			print(d[v[0]])
		else:
			print(0)
	elif '2' == op:
		d[v[0]] = 0
	else:
		left_key = bisect_left(keys, v[0])
		right_key = bisect_right(keys, v[1], left_key)
		for k in range(left_key, right_key):
			if d[keys[k]] > 0:
				print(keys[k], d[keys[k]])


from bisect import *
import sys
n = int(input())
dic = {}
dic2 = {}
box = []
for i in range(n):
	(a, b, *c) = sys.stdin.readline().split()
	if a == '0':
		insort_left(box, b)
		dic[b] = int(c[0])
	elif a == '1':
		print(dic[b] if b in dic else 0)
	elif a == '2':
		if b in dic:
			del dic[b]
	else:
		L = bisect_left(box, b)
		R = bisect_right(box, c[0])
		while L < R:
			if box[L] in dic:
				print(box[L], dic[box[L]])
			L = bisect_right(box, box[L])


from bisect import bisect_left, bisect_right, insort_left
q = int(input())
M = {}
tbl = []
for i in range(q):
	(query, *x) = input().split()
	if query == '0':
		x[1] = int(x[1])
		if x[0] not in M:
			insort_left(tbl, x[0])
		M[x[0]] = x[1]
	elif query == '1':
		print(M[x[0]] if x[0] in M and M[x[0]] != 0 else 0)
	elif query == '2':
		M[x[0]] = 0
	else:
		L = bisect_left(tbl, x[0])
		R = bisect_right(tbl, x[1])
		for i in range(L, R):
			if M[tbl[i]] != 0:
				print(tbl[i], M[tbl[i]])


from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = a[1]
	if a[0] == '0':
		if ki not in dict:
			insort_left(keytbl, ki)
		dict[ki] = int(a[2])
	elif a[0] == '1':
		print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			dict[ki] = 0
	else:
		L = bisect_left(keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			if dict[keytbl[j]] > 0:
				print(keytbl[j], dict[keytbl[j]])


import bisect
q = int(input())
M = {}
sortedList = []
for i in range(q):
	(query, *inp) = input().split()
	key = inp[0]
	if query == '0':
		x = int(inp[1])
		if key not in M:
			bisect.insort_left(sortedList, key)
		M[key] = x
	elif query == '1':
		if key in M:
			if M[key] != None:
				print(M[key])
			else:
				print(0)
		else:
			print(0)
	elif query == '2':
		if key in M:
			M[key] = None
	else:
		L = inp[0]
		R = inp[1]
		index_left = bisect.bisect_left(sortedList, L)
		index_right = bisect.bisect_right(sortedList, R)
		for i in range(index_left, index_right):
			key_ans = sortedList[i]
			if M[key_ans] != None:
				print(key_ans, M[key_ans])


from bisect import bisect, bisect_left, insort
dic = {}
l = []
for i in range(int(input())):
	order = list(input().split())
	if order[0] == '0':
		if order[1] in dic:
			dic[order[1]] = int(order[2])
		else:
			dic[order[1]] = int(order[2])
			insort(l, order[1])
	elif order[0] == '1':
		if order[1] in dic:
			print(dic[order[1]])
		else:
			print(0)
	elif order[0] == '2':
		if order[1] in dic:
			dic[order[1]] = 0
	elif order[0] == '3':
		L = bisect_left(l, order[1])
		R = bisect(l, order[2])
		for i in range(L, R):
			if dic[l[i]]:
				print(l[i], dic[l[i]])


from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = a[1]
	if a[0] == '0':
		if ki not in dict:
			insort_left(keytbl, ki)
		dict[ki] = int(a[2])
	elif a[0] == '1':
		print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			dict[ki] = 0
	else:
		L = bisect_left(keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			if dict[keytbl[j]] > 0:
				print(keytbl[j], dict[keytbl[j]])


q = int(input())
s = []
rs = []
for i in range(q):
	s.append(input().split())
	if s[i][0] == '3':
		rs.append(s[i][1])
		rs.append(s[i][2])
	else:
		rs.append(s[i][1])
rs = sorted(list(set(rs)))
index = {rs[i]: i for i in range(len(rs))}
d = [None for i in range(len(rs))]
for i in range(q):
	(op, key) = (int(s[i][0]), s[i][1])
	idx = index[key]
	if op == 0:
		d[idx] = s[i][2]
	elif op == 1:
		if d[idx] == None:
			print(0)
		else:
			print(d[idx])
	elif op == 2:
		d[idx] = None
	else:
		l = idx
		r = index[s[i][2]]
		for j in range(l, r + 1):
			if d[j] != None:
				print(rs[j], d[j])


from enum import Enum

class Color(Enum):
	BLACK = 0
	RED = 1

	@staticmethod
	def flip(c):
		return [Color.RED, Color.BLACK][c.value]

class Node:
	__slots__ = ('key', 'left', 'right', 'size', 'color', 'value')

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.left = Leaf
		self.right = Leaf
		self.size = 1
		self.color = Color.RED

	def is_red(self):
		return self.color == Color.RED

	def is_black(self):
		return self.color == Color.BLACK

	def __str__(self):
		if self.color == Color.RED:
			key = '*{}'.format(self.key)
		else:
			key = '{}'.format(self.key)
		return '{}[{}] ({}, {})'.format(key, self.size, self.left, self.right)

class LeafNode(Node):

	def __init__(self):
		self.key = None
		self.value = None
		self.left = None
		self.right = None
		self.size = 0
		self.color = None

	def is_red(self):
		return False

	def is_black(self):
		return False

	def __str__(self):
		return '-'
Leaf = LeafNode()

class RedBlackBinarySearchTree:

	def __init__(self):
		self.root = Leaf

	def put(self, key, value=None):

		def _put(node):
			if node is Leaf:
				node = Node(key, value)
			if node.key > key:
				node.left = _put(node.left)
			elif node.key < key:
				node.right = _put(node.right)
			else:
				node.value = value
			node = self._restore(node)
			node.size = node.left.size + node.right.size + 1
			return node
		self.root = _put(self.root)
		self.root.color = Color.BLACK

	def _rotate_left(self, node):
		x = node.right
		node.right = x.left
		x.left = node
		x.color = node.color
		node.color = Color.RED
		node.size = node.left.size + node.right.size + 1
		return x

	def _rotate_right(self, node):
		x = node.left
		node.left = x.right
		x.right = node
		x.color = node.color
		node.color = Color.RED
		node.size = node.left.size + node.right.size + 1
		return x

	def _flip_colors(self, node):
		node.color = Color.flip(node.color)
		node.left.color = Color.flip(node.left.color)
		node.right.color = Color.flip(node.right.color)
		return node

	def __contains__(self, key):

		def _contains(node):
			if node is Leaf:
				return False
			if node.key > key:
				return _contains(node.left)
			elif node.key < key:
				return _contains(node.right)
			else:
				return True
		return _contains(self.root)

	def get(self, key):

		def _get(node):
			if node is Leaf:
				return None
			if node.key > key:
				return _get(node.left)
			elif node.key < key:
				return _get(node.right)
			else:
				return node.value
		return _get(self.root)

	def delete(self, key):

		def _delete(node):
			if node is Leaf:
				return Leaf
			if node.key > key:
				if node.left is Leaf:
					return self._balance(node)
				if not self._is_red_left(node):
					node = self._red_left(node)
				node.left = _delete(node.left)
			else:
				if node.left.is_red():
					node = self._rotate_right(node)
				if node.key == key and node.right is Leaf:
					return Leaf
				elif node.right is Leaf:
					return self._balance(node)
				if not self._is_red_right(node):
					node = self._red_right(node)
				if node.key == key:
					x = self._find_min(node.right)
					node.key = x.key
					node.value = x.value
					node.right = self._delete_min(node.right)
				else:
					node.right = _delete(node.right)
			return self._balance(node)
		if self.is_empty():
			raise ValueError('delete on empty tree')
		if not self.root.left.is_red() and (not self.root.right.is_red()):
			self.root.color = Color.RED
		self.root = _delete(self.root)
		if not self.is_empty():
			self.root.color = Color.BLACK

	def delete_max(self):
		if self.is_empty():
			raise ValueError('delete max on empty tree')
		if not self.root.left.is_red() and (not self.root.right.is_red()):
			self.root.color = Color.RED
		self.root = self._delete_max(self.root)
		if not self.is_empty():
			self.root.color = Color.BLACK

	def _delete_max(self, node):
		if node.left.is_red():
			node = self._rotate_right(node)
		if node.right is Leaf:
			return Leaf
		if not self._is_red_right(node):
			node = self._red_right(node)
		node.right = self._delete_max(node.right)
		return self._balance(node)

	def _red_right(self, node):
		node = self._flip_colors(node)
		if node.left.left.is_red():
			node = self._rotate_right(node)
		return node

	def _is_red_right(self, node):
		return node.right.is_red() or (node.right.is_black() and node.right.left.is_red())

	def delete_min(self):
		if self.is_empty():
			raise ValueError('delete min on empty tree')
		if not self.root.left.is_red() and (not self.root.right.is_red()):
			self.root.color = Color.RED
		self.root = self._delete_min(self.root)
		if not self.is_empty():
			self.root.color = Color.BLACK

	def _delete_min(self, node):
		if node.left is Leaf:
			return Leaf
		if not self._is_red_left(node):
			node = self._red_left(node)
		node.left = self._delete_min(node.left)
		return self._balance(node)

	def _red_left(self, node):
		node = self._flip_colors(node)
		if node.right.left.is_red():
			node.right = self._rotate_right(node.right)
			node = self._rotate_left(node)
		return node

	def _is_red_left(self, node):
		return node.left.is_red() or (node.left.is_black() and node.left.left.is_red())

	def _balance(self, node):
		if node.right.is_red():
			node = self._rotate_left(node)
		return self._restore(node)

	def _restore(self, node):
		if node.right.is_red() and (not node.left.is_red()):
			node = self._rotate_left(node)
		if node.left.is_red() and node.left.left.is_red():
			node = self._rotate_right(node)
		if node.left.is_red() and node.right.is_red():
			node = self._flip_colors(node)
		node.size = node.left.size + node.right.size + 1
		return node

	def is_empty(self):
		return self.root is Leaf

	def is_balanced(self):
		if self.is_empty():
			return True
		try:
			left = self._depth(self.root.left)
			right = self._depth(self.root.right)
			return left == right
		except Exception:
			return False

	@property
	def depth(self):
		return self._depth(self.root)

	def _depth(self, node):
		if node is Leaf:
			return 0
		if node.right.is_red():
			raise Exception('right red')
		left = self._depth(node.left)
		right = self._depth(node.right)
		if left != right:
			raise Exception('unbalanced')
		if node.is_red():
			return left
		else:
			return 1 + left

	def __len__(self):
		return self.root.size

	@property
	def max(self):
		if self.is_empty():
			raise ValueError('max on empty tree')
		return self._max(self.root)

	def _max(self, node):
		x = self._find_max(node)
		return x.key

	def _find_max(self, node):
		if node.right is Leaf:
			return node
		else:
			return self._find_max(node.right)

	@property
	def min(self):
		if self.is_empty():
			raise ValueError('min on empty tree')
		return self._min(self.root)

	def _min(self, node):
		x = self._find_min(node)
		return x.key

	def _find_min(self, node):
		if node.left is Leaf:
			return node
		else:
			return self._find_min(node.left)

	def __iter__(self):

		def inorder(node):
			if node is Leaf:
				return
			yield from inorder(node.left)
			yield node.value
			yield from inorder(node.right)
		yield from inorder(self.root)

	def range(self, min_, max_):

		def _range(node):
			if node is Leaf:
				return
			if node.key > max_:
				yield from _range(node.left)
			elif node.key < min_:
				yield from _range(node.right)
			else:
				yield from _range(node.left)
				yield (node.key, node.value)
				yield from _range(node.right)
		if min_ > max_:
			return
		yield from _range(self.root)

class Map:

	def __init__(self):
		self.tree = RedBlackBinarySearchTree()

	def __getitem__(self, key):
		if key in self.tree:
			return self.tree.get(key)
		else:
			raise IndexError('key {} not found in map'.format(key))

	def __setitem__(self, key, value):
		self.tree.put(key, value)

	def __delitem__(self, key):
		if key in self.tree:
			self.tree.delete(key)
		else:
			raise IndexError('key {} not found in map'.format(key))

	def __len__(self):
		return len(self.tree)

	def items(self):
		for (k, v) in self.tree:
			yield (k, v)

	def range(self, min_, max_):
		for (k, v) in self.tree.range(min_, max_):
			yield (k, v)

def run():
	q = int(input())
	m = Map()
	for _ in range(q):
		(command, *args) = input().split()
		if command == '0':
			key = args[0]
			value = int(args[1])
			m[key] = value
		elif command == '1':
			key = args[0]
			try:
				print(m[key])
			except IndexError:
				print(0)
		elif command == '2':
			key = args[0]
			try:
				del m[key]
			except IndexError:
				pass
		elif command == '3':
			(low, hi) = args
			for (k, v) in m.range(low, hi):
				print(k, v)
		else:
			raise ValueError('invalid command')
run()


import bisect
keys = []
q = int(input())
d = {}

def find(x):
	index = bisect.bisect_left(keys, x)
	if index == len(keys):
		return -1
	if keys[index] == x:
		return index
	else:
		return -1
for _ in range(q):
	query = input().split(' ')
	if query[0] == '0':
		if find(query[1]) != -1:
			pass
		else:
			bisect.insort_left(keys, query[1])
		d[query[1]] = query[2]
	elif query[0] == '1':
		if find(query[1]) != -1:
			print(d[query[1]])
		else:
			print(0)
	elif query[0] == '2':
		while find(query[1]) >= 0:
			keys.pop(find(query[1]))
	else:
		(L, R) = (query[1], query[2])
		indL = bisect.bisect_left(keys, L)
		indR = bisect.bisect_right(keys, R)
		for s in keys[indL:indR]:
			print(s, d[s])


from bisect import bisect_left, bisect_right, insort_left
a = []
q = int(input())
for i in range(q):
	a.append(list(input().split()))
S = {}
W = []
for i in range(q):
	if a[i][0] == '0':
		if not a[i][1] in S:
			insort_left(W, a[i][1])
		S[a[i][1]] = int(a[i][2])
	elif a[i][0] == '1':
		if a[i][1] in S:
			print(S[a[i][1]])
		else:
			print(0)
	elif a[i][0] == '2':
		if a[i][1] in S:
			S[a[i][1]] = 0
	else:
		L = bisect_left(W, a[i][1])
		R = bisect_right(W, a[i][2])
		for j in range(L, R):
			if S[W[j]] > 0:
				print(W[j], S[W[j]])


import bisect
M = []
D = []
N = []
count = 0

def insert(M, D, N, count, key, x):
	y = bisect.bisect_left(D, key)
	if y < count and D[y] == key:
		M[y][1] = x
		N[y] = x
	else:
		M.insert(y, [key, x])
		D.insert(y, key)
		N.insert(y, x)
		count += 1
	return (M, D, N, count)

def get(D, N, count, key):
	y = bisect.bisect_left(D, key)
	if y < count and D[y] == key:
		print(N[y])
	else:
		print(0)

def erase(M, D, N, count, key):
	y = bisect.bisect_left(D, key)
	if y < count and D[y] == key:
		M.pop(y)
		D.pop(y)
		N.pop(y)
		count -= 1
	return (M, D, N, count)

def dump(M, D, N, L, R):
	s = bisect.bisect_left(D, L)
	e = bisect.bisect_right(D, R)
	if e - s > 0:
		for i in range(s, e):
			print(M[i][0] + ' ' + str(M[i][1]))
q = int(input())
for i in range(q):
	query = list(map(str, input().split()))
	query[0] = int(query[0])
	if query[0] == 0:
		(M, D, N, count) = insert(M, D, N, count, query[1], int(query[2]))
	elif query[0] == 1:
		get(D, N, count, query[1])
	elif query[0] == 2:
		(M, D, N, count) = erase(M, D, N, count, query[1])
	else:
		dump(M, D, N, query[1], query[2])