For a set $S$ of integers, perform a sequence of the following operations. Note that multiple elements can have equivalent values in $S$.

* insert($x$): Insert $x$ to $S$ and report the number of elements in $S$ after the operation.
* find($x$): Report the number of $x$ in $S$.
* delete($x$): Delete all $x$ from $S$.
* dump($L$, $R$): Print elements $x$ in $S$ such that $L \leq x \leq R$.

Constraints

* $1 \leq q \leq 200,000$
* $0 \leq x \leq 1,000,000,000$
* The total number of elements printed by dump operations does not exceed $1,000,000$
* The sum of numbers printed by find operations does not exceed $2,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 $x$


or


1 $x$


or


2 $x$


or


3 $L$ $R$


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

Output

For each insert operation, print the number of elements in $S$.
For each find operation, print the number of specified elements in $S$.
For each dump operation, print the corresponding elements in ascending order. Print an element in a line.

Example

Input

10
0 1
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 1 4


Output

1
2
3
4
2
0
1
4
1
1
3
4

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import bisect
import collections

def main6():
	values = collections.defaultdict(int)
	element_count = 0
	q = int(input())
	for _ in range(q):
		(com, *para) = map(int, input().split())
		if com == 0:
			values[para[0]] += 1
			element_count += 1
			print(element_count)
		elif com == 1:
			print(values[para[0]])
		elif com == 2:
			element_count -= values[para[0]]
			values[para[0]] = 0
		elif com == 3:
			if para[0] == para[1]:
				for _ in range(values[para[0]]):
					print(para[0])
			elif abs(para[0] - para[1]) < 10:
				for i in range(para[0], para[1] + 1):
					for _ in range(values[i]):
						print(i)
			else:
				key_list = [k for (k, v) in values.items() if v != 0]
				key_list = sorted(key_list)
				lb = bisect.bisect_left(key_list, para[0])
				rb = bisect.bisect_right(key_list, para[1])
				for s in key_list[lb:rb]:
					for _ in range(values[s]):
						print(s)
main6()


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


import bisect
S = []

def insert(S, count, x):
	y = bisect.bisect(S, x)
	S.insert(y, x)
	count += 1
	print(count)
	return (S, count)

def find(S, x):
	y0 = bisect.bisect_left(S, x)
	y1 = bisect.bisect_right(S, x)
	return (y0, y1)

def erase(S, count, x):
	(y0, y1) = find(S, x)
	if y1 - y0 > 0:
		del S[y0:y1]
		count -= y1 - y0
	return (S, count)

def dump(S, L, R):
	s = bisect.bisect_left(S, L)
	e = bisect.bisect_right(S, R)
	if e - s > 0:
		print('\n'.join(map(str, S[s:e])))
q = int(input())
count = 0
for i in range(q):
	query = list(map(int, input().split()))
	if query[0] == 0:
		(S, count) = insert(S, count, query[1])
	elif query[0] == 1:
		(y0, y1) = find(S, query[1])
		print(y1 - y0)
	elif query[0] == 2:
		(S, count) = erase(S, count, query[1])
	else:
		dump(S, query[1], query[2])


import sys
import bisect
s = []
input()
for q in sys.stdin:
	q = q.split()
	q[1:] = list(map(int, q[1:]))
	if q[0] == '0':
		bisect.insort_left(s, q[1])
		print(len(s))
	elif q[0] == '1':
		first = bisect.bisect_left(s, q[1])
		end = bisect.bisect_right(s, q[1])
		print(end - first)
	elif q[0] == '2':
		first = bisect.bisect_left(s, q[1])
		end = bisect.bisect_right(s, q[1])
		del s[first:end]
	else:
		first = bisect.bisect_left(s, q[1])
		end = bisect.bisect_right(s, q[2])
		if first != end:
			print('\n'.join(list(map(str, [i for i in s[first:end]]))))


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 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 BalancedBstCounter:

	def __init__(self):
		self.bst = RedBlackBinarySearchTree()
		self.count = 0

	def up(self, key):
		if key in self.bst:
			value = self.bst.get(key) + 1
		else:
			value = 1
		self.bst.put(key, value)
		self.count += 1

	def __contains__(self, key):
		if key in self.bst:
			return self.bst.get(key) > 0
		else:
			return False

	def get(self, key):
		if key in self.bst:
			return self.bst.get(key)
		else:
			return 0

	def down(self, key):
		if key in self.bst:
			value = self.bst.get(key)
			self.bst.put(key, 0)
			self.count -= value

	def range(self, a, b):
		for (k, v) in self.bst.range(a, b):
			for _ in range(v):
				yield k

	def __len__(self):
		return self.count

	def __str__(self):
		return str(self.bst.root)

def run():
	q = int(input())
	counter = BalancedBstCounter()
	for _ in range(q):
		(command, *value) = [int(x) for x in input().split()]
		if command == 0:
			counter.up(value[0])
			print(len(counter))
		elif command == 1:
			print(counter.get(value[0]))
		elif command == 2:
			counter.down(value[0])
		elif command == 3:
			for i in counter.range(*value):
				print(i)
		else:
			raise ValueError('invalid command')
run()


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


import bisect
q = int(input())
S = []
for _ in range(q):
	(command, *list_num) = input().split()
	x = int(list_num[0])
	index_left_x = bisect.bisect_left(S, x)
	index_right_x = bisect.bisect_right(S, x)
	if command == '0':
		x = int(list_num[0])
		S.insert(index_left_x, x)
		print(len(S))
	elif command == '1':
		x = int(list_num[0])
		print(index_right_x - index_left_x)
	elif command == '2':
		x = int(list_num[0])
		S[index_left_x:index_right_x] = []
	elif command == '3':
		L = x
		R = int(list_num[1])
		index_left = bisect.bisect_left(S, L)
		index_right = bisect.bisect_right(S, R)
		for element in S[index_left:index_right]:
			print(element)
	else:
		raise


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


from bisect import insort, bisect_right, bisect_left

class Multi_set:

	def __init__(self):
		self.total = 0
		self.ms = dict()
		self.lr = []

	def insert(self, x):
		self.total += 1
		if x in self.ms:
			self.ms[x] += 1
		else:
			self.ms[x] = 1
			insort(self.lr, x)
		print(self.total)

	def find(self, x):
		print(self.ms.get(x, 0))

	def delete(self, x):
		if x in self.ms:
			self.total -= self.ms[x]
			self.ms[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]
			v = self.ms[k]
			print(f'{k}\n' * v, end='')
ms = Multi_set()
for _ in range(int(input())):
	(op, x, y) = (input() + ' 1').split()[:3]
	if op == '0':
		ms.insert(int(x))
	elif op == '1':
		ms.find(int(x))
	elif op == '2':
		ms.delete(int(x))
	else:
		ms.dump(int(x), int(y))


from bisect import insort, bisect_right, bisect_left

class MultiSet:

	def __init__(self) -> None:
		self.total = 0
		self.ms: dict = dict()
		self.lr: list = []

	def insert(self, x: int) -> None:
		self.total += 1
		if x in self.ms:
			self.ms[x] += 1
		else:
			self.ms[x] = 1
			insort(self.lr, x)
		print(self.total)

	def find(self, x: int) -> None:
		print(self.ms.get(x, 0))

	def delete(self, x: int) -> None:
		if x in self.ms:
			self.total -= self.ms[x]
			self.ms[x] = 0

	def dump(self, l: int, r: int) -> None:
		lb = bisect_left(self.lr, l)
		ub = bisect_right(self.lr, r)
		for i in range(lb, ub):
			k = self.lr[i]
			v = self.ms[k]
			print(f'{k}\n' * v, end='')
ms = MultiSet()
num_query = int(input())
for _ in range(num_query):
	(op, *v) = map(lambda x: int(x), input().split())
	if 0 == op:
		ms.insert(v[0])
	elif 1 == op:
		ms.find(v[0])
	elif 2 == op:
		ms.delete(v[0])
	else:
		ms.dump(v[0], v[1])


import bisect
q = int(input())
S = []
for i in range(q):
	(query, *n) = input().split()
	x = int(n[0])
	index_left = bisect.bisect_left(S, x)
	index_right = bisect.bisect_right(S, x)
	if query[0] == '0':
		x = int(n[0])
		S.insert(index_left, x)
		print(len(S))
	elif query[0] == '1':
		x = int(n[0])
		print(index_right - index_left)
	elif query[0] == '2':
		x = int(n[0])
		S[index_left:index_right] = []
	else:
		L = int(n[0])
		R = int(n[1])
		index_left = bisect.bisect_left(S, L)
		index_right = bisect.bisect_right(S, R)
		[print(i) for i in S[index_left:index_right]]


q = int(input())
s = []
rs = []
for i in range(q):
	s.append(list(map(int, input().split())))
	if s[i][0] == 3:
		rs.append(s[i][1])
		rs.append(s[i][2])
	else:
		rs.append(s[i][1])
rs.append(10 ** 9 + 1)
rs = sorted(list(set(rs)))
index = {rs[i]: i for i in range(len(rs))}
counter = [0 for i in range(len(rs) + 1)]
cnt = 0
for i in range(q):
	(op, x) = (s[i][0], s[i][1])
	idx = index[x]
	if op == 0:
		cnt += 1
		counter[idx] += 1
		print(cnt)
	elif op == 1:
		print(counter[idx])
	elif op == 2:
		cnt -= counter[idx]
		counter[idx] = 0
	else:
		l = idx
		r = index[s[i][2]]
		for j in range(l, r + 1):
			for k in range(counter[j]):
				print(rs[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):
		assert node.right.is_red()
		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):
		assert node.left.is_red()
		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
		assert self.is_balanced()

	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
		assert self.is_balanced()

	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
		assert self.is_balanced()

	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 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 BalancedBstCounter:

	def __init__(self):
		self.bst = RedBlackBinarySearchTree()
		self.count = 0

	def up(self, key):
		if key in self.bst:
			value = self.bst.get(key) + 1
		else:
			value = 1
		self.bst.put(key, value)
		self.count += 1

	def __contains__(self, key):
		if key in self.bst:
			return self.bst.get(key) > 0
		else:
			return False

	def get(self, key):
		if key in self.bst:
			return self.bst.get(key)
		else:
			return 0

	def down(self, key):
		if key in self.bst:
			value = self.bst.get(key)
			self.bst.put(key, 0)
			self.count -= value

	def range(self, a, b):
		for (k, v) in self.bst.range(a, b):
			for _ in range(v):
				yield k

	def __len__(self):
		return self.count

	def __str__(self):
		return str(self.bst.root)

def run():
	q = int(input())
	counter = BalancedBstCounter()
	for _ in range(q):
		(command, *value) = [int(x) for x in input().split()]
		if command == 0:
			counter.up(value[0])
			print(len(counter))
		elif command == 1:
			print(counter.get(value[0]))
		elif command == 2:
			counter.down(value[0])
		elif command == 3:
			for i in counter.range(*value):
				print(i)
		else:
			raise ValueError('invalid command')
run()


q = int(input())
s = []
rs = []
for i in range(q):
	s.append(list(map(int, input().split())))
	if s[i][0] == 3:
		rs.append(s[i][1])
		rs.append(s[i][2])
	else:
		rs.append(s[i][1])
rs.append(10 ** 9 + 1)
rs = sorted(list(set(rs)))
index = {rs[i]: i for i in range(len(rs))}
counter = [0 for i in range(len(rs) + 1)]
cnt = 0
for i in range(q):
	(op, x) = (s[i][0], s[i][1])
	idx = index[x]
	if op == 0:
		cnt += 1
		counter[idx] += 1
		print(cnt)
	elif op == 1:
		print(counter[idx])
	elif op == 2:
		cnt -= counter[idx]
		counter[idx] = 0
	else:
		l = idx
		r = index[s[i][2]]
		for j in range(l, r + 1):
			for k in range(counter[j]):
				print(rs[j])


import bisect
S = []
q = int(input())

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


from bisect import bisect_left, bisect_right, insort_left
dict = {}
li = []
count = 0
q = int(input())
for i in range(q):
	a = input().split()
	t = int(a[1])
	if a[0] == '0':
		if t not in dict:
			dict[t] = 1
			insort_left(li, t)
		else:
			dict[t] += 1
		count += 1
		print(count)
	elif a[0] == '1':
		print(dict[t] if t in dict else 0)
	elif a[0] == '2':
		if t in dict:
			count -= dict[t]
			dict[t] = 0
	else:
		l = bisect_left(li, int(a[1]))
		r = bisect_right(li, int(a[2]))
		lis = []
		for i in range(l, r):
			lis += [li[i]] * dict[li[i]]
		if lis != []:
			print(*lis, sep='\n')


import bisect
import sys

def input():
	return sys.stdin.readline().strip()
S = []
count = {}
total = 0
for _ in range(int(input())):
	order = tuple(map(int, input().split()))
	value = order[1]
	if order[0] == 0:
		if value in count:
			count[value] += 1
		else:
			count[value] = 1
			bisect.insort(S, value)
		total += 1
		print(total)
	elif order[0] == 1:
		if value in count:
			print(count[value])
		else:
			print(0)
	elif order[0] == 2:
		if value in count:
			total -= count[value]
			count[value] = 0
	else:
		left = bisect.bisect_left(S, order[1])
		right = bisect.bisect(S, order[2])
		out = []
		for i in range(left, right):
			out += [S[i]] * count[S[i]]
		for i in out:
			print(i)


from bisect import *
import sys
n = int(input())
ss = []
color = {}
cnt = 0
for _ in range(n):
	(a, b, *c) = map(int, sys.stdin.readline().split())
	if a == 0:
		if b not in color:
			insort_left(ss, b)
			color[b] = 1
			cnt += 1
		else:
			color[b] += 1
			cnt += 1
		print(cnt)
	elif a == 1:
		print(color[b] if b in color else 0)
	elif a == 2:
		if b in color:
			cnt -= color[b]
			color[b] = 0
	else:
		L = bisect_left(ss, b)
		R = bisect(ss, c[0])
		for i in range(L, R):
			for _ in range(color[ss[i]]):
				print(ss[i])


import sys
import bisect
nq = int(input())
lines = sys.stdin.readlines()
ans = [None] * nq
arr = []
for i in range(nq):
	(q, *arg) = lines[i].split()
	x = int(arg[0])
	l_idx = bisect.bisect_left(arr, x)
	r_idx = bisect.bisect_right(arr, x)
	if q == '0':
		arr.insert(l_idx, x)
		ans[i] = str(len(arr))
	elif q == '1':
		ans[i] = r_idx - l_idx
	elif q == '2':
		arr[l_idx:r_idx] = []
	else:
		r_idx = bisect.bisect_right(arr, int(arg[1]))
		ans[i] = '\n'.join(map(str, arr[l_idx:r_idx])) if l_idx != r_idx else None
[print(x) for x in ans if x is not None]