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 multiple elements can have equivalent keys.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$.
* get($key$): Print all values with the specified $key$.
* delete($key$): Delete all elements 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 get operations does not exceed $500,000$
* The total number of elements printed by dump operations does not exceed $500,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 values in the order of insertions.
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 in ascending order of the keys, in case of a tie, in the order of insertions.

Example

Input

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


Output

1
6
4
white 5

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from bisect import insort, bisect_right, bisect_left

class Multi_map:

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

	def insert(self, x, y):
		if x in self.mm:
			self.mm[x].append(y)
		else:
			self.mm[x] = [y]
			insort(self.lr, x)

	def get(self, x):
		if x in self.mm and self.mm[x] != []:
			print(*self.mm[x], sep='\n')

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

	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]
			for v in self.mm[k]:
				print(f'{k} {v}')
mm = Multi_map()
for _ in range(int(input())):
	(op, x, y) = (input() + ' 1').split()[:3]
	if op == '0':
		mm.insert(x, int(y))
	elif op == '1':
		mm.get(x)
	elif op == '2':
		mm.delete(x)
	else:
		mm.dump(x, y)


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:
			dict[ki] = []
			insort_left(keytbl, ki)
		dict[ki].append(int(a[2]))
	elif a[0] == '1':
		if ki in dict and dict[ki] != []:
			print(*dict[ki], sep='\n')
	elif a[0] == '2':
		if ki in dict:
			dict[ki] = []
	else:
		L = bisect_left(keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			for k in dict[keytbl[j]]:
				print(keytbl[j], k)


import bisect
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:
			dict[ki] = []
			insort_left(keytbl, ki)
		dict[ki].append(int(a[2]))
	elif a[0] == '1' and ki in dict and (dict[ki] != []):
		print(*dict[ki], sep='\n')
	elif a[0] == '2' and ki in dict:
		dict[ki] = []
	elif a[0] == '3':
		L = bisect_left(keytbl, a[1])
		R = bisect_right(keytbl, a[2])
		for j in range(L, R):
			for k in dict[keytbl[j]]:
				print(keytbl[j], k)


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] = []
		M[key].append(x)
	elif command == '1':
		key = list_num[0]
		if key in M:
			if M[key]:
				for value in M[key]:
					print(value)
	elif command == '2':
		key = list_num[0]
		if key in M:
			M[key] = []
	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]:
				for value_ans in M[key_ans]:
					print(key_ans, value_ans)
	else:
		raise


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 = [[] 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].append(s[i][2])
	elif op == 1:
		for item in d[idx]:
			print(item)
	elif op == 2:
		d[idx].clear()
	else:
		l = idx
		r = index[s[i][2]]
		for j in range(l, r + 1):
			for item in d[j]:
				print(rs[j], item)


import bisect
M = {}
D = []

def insert(M, D, key, x):
	if key not in M:
		M[key] = []
		bisect.insort_left(D, key)
	M[key].append(x)
	return (M, D)

def get(M, D, key):
	if key in M and M[key] != []:
		print('\n'.join(map(str, M[key])))

def erase(M, D, key):
	if key in M:
		M[key] = []
	return (M, D)

def dump(M, D, L, R):
	s = bisect.bisect_left(D, L)
	e = bisect.bisect_right(D, R)
	if e - s > 0:
		for i in range(s, e):
			for j in M[D[i]]:
				print(D[i], j)
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) = insert(M, D, query[1], int(query[2]))
	elif query[0] == 1:
		get(M, D, query[1])
	elif query[0] == 2:
		(M, D) = erase(M, D, query[1])
	else:
		dump(M, D, query[1], query[2])


import bisect
q = int(input())
M = {}
sortedList = []
for value 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] = []
		M[key].append(x)
	elif query == '1':
		if key in M:
			if M[key]:
				for value in M[key]:
					print(value)
	elif query == '2':
		if key in M:
			M[key] = []
	else:
		L = inp[0]
		R = inp[1]
		index_left = bisect.bisect_left(sortedList, L)
		index_right = bisect.bisect_right(sortedList, R)
		for value in range(index_left, index_right):
			keyAns = sortedList[value]
			if M[keyAns]:
				for valueAns in M[keyAns]:
					print(keyAns, valueAns)


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


import sys
import bisect
from collections import defaultdict
n = int(input())
arr = []
d = defaultdict(list)
lines = sys.stdin.readlines()
ans = [None] * n
for i in range(n):
	(q, *arg) = lines[i].split()
	key = arg[0]
	l_idx = bisect.bisect_left(arr, arg[0])
	r_idx = bisect.bisect_right(arr, arg[0])
	if q == '0':
		if l_idx == len(arr) or arr[l_idx] != key:
			arr.insert(l_idx, key)
		d[key].append(arg[1])
	elif q == '1':
		if l_idx != r_idx:
			ans[i] = '\n'.join(d[key])
	elif q == '2':
		arr[l_idx:r_idx] = []
		if l_idx != r_idx:
			del d[key]
	elif q == '3':
		r_idx = bisect.bisect_right(arr, arg[1])
		if l_idx != r_idx:
			keys = arr[l_idx:r_idx]
			ans[i] = '\n'.join(['\n'.join([f'{k} {x}' for x in d[k]]) for k in keys])
[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:
			dict[ki] = []
			insort_left(keytbl, ki)
		dict[ki].append(int(a[2]))
	elif a[0] == '1':
		if ki in dict and dict[ki] != []:
			print(*dict[ki], sep='\n')
	elif a[0] == '2':
		if ki in dict:
			dict[ki] = []
	else:
		L = bisect_left(keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			for k in dict[keytbl[j]]:
				print(keytbl[j], k)


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:
			item = d[query[1]]
		else:
			bisect.insort_left(keys, query[1])
			item = []
		item.append(query[2])
		d[query[1]] = item
	elif query[0] == '1':
		if find(query[1]) != -1:
			for item in d[query[1]]:
				print(item)
	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]:
			for item in d[s]:
				print(s, item)


from bisect import bisect_left, bisect_right, insort_left
from typing import Dict, List
num_query = int(input())
d: Dict[str, List[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]] = []
		d[v[0]].append(int(v[1]))
	elif '1' == op:
		if v[0] in d:
			for elem in d[v[0]]:
				print(elem)
	elif '2' == op:
		if v[0] in d:
			d[v[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):
			for elem in d[keys[k]]:
				print(keys[k], elem)


from bisect import *
n = int(input())
dic = {}
dic2 = {}
box = []
for i in range(n):
	(a, b, *c) = input().split()
	if a == '0':
		insort_left(box, b)
		if b in dic:
			temp = dic[b]
			dic[b] = temp + [int(c[0])]
		else:
			dic[b] = [int(c[0])]
	elif a == '1':
		if b in dic:
			pri = []
			for i in dic[b]:
				pri.append(str(i))
			print('\n'.join(pri))
	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:
				for i in dic[box[L]]:
					print(box[L], i)
			L = bisect_right(box, box[L])


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()
		self.count = 0

	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):
		if key in self.tree:
			values = self.tree.get(key)
			values += (value,)
		else:
			values = (value,)
		self.tree.put(key, values)
		self.count += 1

	def __delitem__(self, key):
		if key in self.tree:
			values = self.tree.get(key)
			self.tree.put(key, tuple())
			self.count -= len(values)
		else:
			raise IndexError('key {} not found in map'.format(key))

	def __len__(self):
		return self.count

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

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

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:
				for value in m[key]:
					print(value)
			except IndexError:
				pass
		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
from collections import defaultdict

def main():
	q = int(input())
	d = defaultdict(list)
	inserted_flag = False
	sorted_keys = None
	for _ in range(q):
		para = input().split()
		if para[0] == '0':
			d[para[1]].append(int(para[2]))
			inserted_flag = True
		elif para[0] == '1':
			if para[1] in d.keys():
				for i in range(len(d[para[1]])):
					print(d[para[1]][i])
		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):
				for j in range(len(d[sorted_keys[i]])):
					print('{} {}'.format(sorted_keys[i], d[sorted_keys[i]][j]))
main()