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

Solution (in CPP):

Solution:
// #include<initializer_list>
// #include<iostream>

#include<iostream>
using namespace std;

template<typename type>
class BTree {
public :
	static const int default_min_degree = 2;
	bool MULTISET = true; // true -> duplicate 　false -> not duplicate 
	int SEARCH = 0; // linear search ->0  binary search ->1
	bool COUNT_NUM = true;
	
	int number_of_element;
	int min_degree;
	
	
	class Node {
	public :
		bool leaf;
		int number_of_key;
		int w_num;
		
		Node* parent;
		// int *count;
		int *sum;
		type *key;
		Node** children;
		BTree<type>* btree;
		
		Node(BTree<type>* btree, Node* parent = nullptr): btree(btree), parent(parent) {init();}	
		
		~Node(){
			delete[] sum;
			delete[] key;
			delete[] children;
		}
		
		void init() {
			leaf = true;
			number_of_key = 0;
			w_num = 0;
			// count = 1;
			
			key = new type[btree->min_degree * 2 - 1];
			children = new Node*[btree->min_degree * 2];
			
			if(btree->COUNT_NUM) {
				sum = new int[btree->min_degree * 2];
				sum[0] = 0;
			}
			
		}
	};
	
	Node* root;
	
	
	class jnode {
	public:
		Node* node;
		int index;
		
		jnode(Node* node = nullptr, int index = -1): node(node), index(index){}	
		jnode(const jnode &j) { node = j.node;  index = j.index;};
		
		jnode& operator ++(){
			
			
				
			if(node == nullptr) { //cout<<"A"<<endl;
				index = -2;
			} else if(node->number_of_key <= index){//cout<<"B"<<endl;
				
				do{
					index = node->w_num;
					node = node->parent;
				} while(node != nullptr && node->number_of_key <= index);
				
			} else if(node->leaf) { 
				if(node->number_of_key - 1 <= index) { //cout<<"C"<<endl;
					do{
						index = node->w_num;
						node = node->parent;
					} while(node != nullptr && node->number_of_key <= index);
				
				} else { //cout<<"D"<<endl;
					index++;
				}
			} else { //cout<<"E"<<endl;
				node = node->children[index+1];
				
				while(!node->leaf){
					node = node->children[0];
				}
				
				index = 0;
			}
			
			return *this;
		}
		
		jnode operator ++(int) {
			jnode j = *this;
			
			++(*this);
			
			return j;
		}
		
		jnode& operator --(){
			
			if(node == nullptr) {
				index = -1;
			} else if(index < 0){
				do{
					index = node->w_num - 1;
					node = node->parent;
				} while(node != nullptr && index < 0);
				
			} else if(node->leaf) {
				if(index == 0) {
					do{
						index = node->w_num - 1;
						node = node->parent;
					} while(node != nullptr && index < 0);
				} else {
					index--;
				}
			} else {
				node = node->children[index];
				
				while(!node->leaf){
					node = node->children[node->children->number_of_key];
				}
				
				index = node->number_of_key - 1;
			}
			return *this;
		}
		
		jnode operator --(int) {
			jnode j = *this;
			
			--(*this);
			
			return j;
		}		
		
		bool operator == (const jnode &j) const {
			return node ==  j.node && index == j.index;
		}
	};
	
	
	BTree(int min_degree = default_min_degree) : min_degree(min_degree){ create();};
	
	~BTree(){
		clear(root);
	}
	
	int index_search(Node *node, int key, int k){  // lower bound
		int index;
		
		if(k == 0){
			// linear search
			
			for(index = 0; index < node->number_of_key && (node->key[index] < key); index++);
		} else if(k == 1){
			//binary search
			
			index = node->number_of_key;
			int low = -1, med;
			while(low + 1< index){
				int med = (low + index) >> 1;
				
				if((node->key[med] < key)) {
					low = med;
				} else {
					index = med;
				}
			}
		}
		
		return index;
	}
	
	int index_search2(Node *node, int key, int k){ // upper bound
		int index;
		
		if(k == 0){
			// linear search
			
			for(index = 0; index < node->number_of_key && (key >= node->key[index]); index++);
		} else if(k == 1){
			//binary search
			
			index = node->number_of_key;
			int low = -1, med;
			while(low + 1 < index){
				int med = (low + index) >> 1;
				
				if(key >= node->key[med]) {
					low = med;
				} else {
					index = med;
				}
			}
		}
		
		return index;
	}
	
	int sum_search(Node *node, int num, int k){
		int index = 0;
		
		if(k == 0){
			// linear search
			
			for(index = 0; index < node->number_of_key && node->sum[index] < num; index++);
		} else if(k == 1){
			//binary search
			
			index = node->number_of_key;
			int low = -1, med;
			while(low + 1 < index){
				int med = (low + index) >> 1;
				
				if(node->sum[med] < num) {
					low = med;
				} else {
					index = med;
				}
			}
		}
		
		return index;
	}
	
	void clear(Node* node){
		
		if(!node->leaf) {
			for(int i = 0; i <= node->number_of_key; i++){
				clear(node->children[i]);
			}
		}
		
		delete node;
	}
	
	void create(){
		number_of_element = 0;
		
		root = new Node(this);
	}
	
	int lower_bound(type key){
		return lower_bound(root, key);
	}
	
	int lower_bound(Node *node, type key){
		int index = index_search(node, key, SEARCH);
		
		if(node->leaf) {
			if(index < node->number_of_key) return node->sum[index];
			else return node->number_of_key;
		} else {
			 if(index) return lower_bound(node->children[index], key) + node->sum[index-1] + 1;
			else return lower_bound(node->children[index], key);
		}
	}
	
	int upper_bound(type key){
		return upper_bound(root, key);
	}
	
	int upper_bound(Node *node, type key){
		int index = index_search2(node, key, SEARCH);
		
		if(node->leaf) {
			if(index < node->number_of_key) return node->sum[index];
			else return node->number_of_key;
		} else {
			 if(index) return upper_bound(node->children[index], key) + node->sum[index-1] + 1;
			else return upper_bound(node->children[index], key);
		}
	}
	
	int size(){
		return number_of_element;
	}
	
	Node* search(type k){
		return search(root, k);
	}
	
	Node* search(Node* node, type key){
		
		int index = index_search(node, key, SEARCH);
		
		
		if(index < node->number_of_key && (node->key[index] == key)) {
			return node;
		} else if(node->leaf) {
			return nullptr;
		} else {
			return search(node->children[index], key);
		}
	}
	
	void operation(Node *node, int index = 0){
		if(COUNT_NUM) count_number(node, index);
		change_w_num(node, index);
	}
	
	void count_number(Node *node, int index){
		
		if(node == nullptr) return;
		
		if(node->leaf) {
			for(int i = index; i <= node->number_of_key; i++) {
				node->sum[i] = 0;
				if(i) {
					node->sum[i] += node->sum[i-1] + 1;
					// node->sum[i] += node->sum[i-1] + node->count[i-1];
				}
			}
		} else {
			for(int i = index; i <= node->number_of_key; i++){
				
				node->sum[i] = node->children[i]->sum[node->children[i]->number_of_key];
			
				if(i) {
					node->sum[i] += node->sum[i-1] + 1;
				}
			}
		}
	}
	
	void change_w_num(Node *node, int index){
		if(node == nullptr) return;
		if(node == root) node->parent = nullptr;
		
		if(!node->leaf) {
			for(int i = index; i <= node->number_of_key; i++){
				node->children[i]->w_num = i;
				node->children[i]->parent = node;
			}
		}
	}
	
	
	jnode nth_element(int num){
		if(num < 0 || num >= size()) return jnode();
		return nth_element(root, num);
	}
	
	jnode nth_element(Node* node, int num){
		int index = sum_search(node, num, SEARCH);
		
		if(index < node->number_of_key && num == node->sum[index]) {
			return jnode(node, index);
		} else {
			if(node->leaf) {
				// どうしてここに？
			} else {
				if(index) return nth_element(node->children[index], num - node->sum[index-1] - 1);
				else return nth_element(node->children[index], num);
			}
		}
	}
	
	void split_child(Node* node, int index){
		Node *right_child = new Node(this, node);
		Node *left_child = node->children[index];
		
		right_child->leaf =  left_child->leaf;
		right_child->number_of_key = min_degree - 1;
		
		for(int j = 0; j < min_degree - 1; j++){
			right_child->key[j] = left_child->key[j + min_degree];
		}
		
		if(!left_child->leaf) {
			
			for(int j = 0; j < min_degree; j++){
				right_child->children[j] = left_child->children[j + min_degree];
			}
			
		}
		
		left_child->number_of_key = min_degree - 1;
		
		for(int j = node->number_of_key; j > index; j--){
			node->children[j+1] = node->children[j];
		}
		
		node->children[index+1] = right_child;
		
		for(int j = node->number_of_key - 1; j >= index; j--){
			node->key[j+1] = node->key[j];
		}
		
		node->key[index] = left_child->key[min_degree-1];
		
		node->number_of_key++;
		
		right_child->parent = node;
		
		operation(right_child);
		operation(left_child);
	}
	
	void insert_nonfull(Node* node, type key){
		int index = node->number_of_key - 1;
		
		if(node->leaf) {
			
			for(; index >= 0 && (key < node->key[index]); index--){
				node->key[index+1] = node->key[index];
			}
			
			node->key[index+1] = key;
			node->number_of_key++;
		} else {
			for(; index >= 0 && (key < node->key[index]); index--);
			
			index++;
			
			if(node->children[index]->number_of_key == 2 * min_degree - 1) {
				split_child(node, index);
				
				if((node->key[index] < key)) index++;
			}
			
			insert_nonfull(node->children[index], key);
		}
		
		operation(node);
	}
	
	void insert(type key){
		if(!MULTISET && search(key) != nullptr) return ;
		
		number_of_element++;
		
		_insert(key);
	}
	
	void _insert(type key){
		Node* temp_root = root;
		
		if(root->number_of_key == 2 * min_degree - 1) {
			Node* new_node = new Node(this);
			
			root = new_node;
			
			root->leaf = false;
			root->children[0] = temp_root;
			root->parent = new_node;
			

			split_child(root, 0);
			insert_nonfull(root, key);
		} else {
			insert_nonfull(root, key);
		}
	}
	
	void erase(type key){
		erase(root, key);
		
		while(root->number_of_key == 0 && !root->leaf) {
			Node *temp = root;
			
			root = root->children[0];
			root->parent = nullptr;		
			
			delete temp;
		}
	}
	
	void erase(Node* node, type key){
		int index = index_search(node, key, SEARCH);
		
		if(index < node->number_of_key && (node->key[index] == key)) {
			if(node->leaf) {
				for(int i = index; i + 1 < node->number_of_key; i++){
					node->key[i] = node->key[i + 1];
				}
				
				number_of_element--;
				node->number_of_key--;
				
			} else {
				Node* child1 = node->children[index];
				Node* child2 = node->children[index+1];
				
				if(child1->number_of_key >= min_degree) {
					Node *maximum = child1;
					
					while(!maximum->leaf){
						maximum = maximum->children[maximum->number_of_key];
					}
					
					node->key[index] = maximum->key[maximum->number_of_key-1];
					
					erase(child1, node->key[index]);
				} else if(child2->number_of_key >= min_degree){
					Node *minimum = child2;
					
					while(!minimum->leaf){
						minimum = minimum->children[0];
					}
				
					node->key[index] = minimum->key[0];
					
					erase(child2, node->key[index]);
				} else {
					
					child1->key[min_degree - 1] = key;
					
					for(int i = min_degree; i < min_degree * 2 - 1; i++){
						child1->key[i] = child2->key[i - min_degree];
					}
					
					for(int i = min_degree; i < min_degree * 2; i++){
						child1->children[i] = child2->children[i - min_degree];
					}
					
					delete child2;
					
					child1->number_of_key = min_degree * 2 - 1;
					
					for(int i = index; i + 1 < node->number_of_key; i++){
						node->key[i] = node->key[i + 1];
					}
					for(int i = index + 1; i < node->number_of_key; i++){
						node->children[i] = node->children[i + 1];
					}
					
					node->number_of_key--;
					
					erase(child1, key);
				}
			}
		} else if(node->leaf) {
		
		} else {
		
			Node* child0 = nullptr;
			Node* child1 = child1 = node->children[index];;
			Node* child2 = nullptr;
			
			if(index >= 1) child0 = node->children[index-1];
			if(index + 1 <= node->number_of_key) child2 = node->children[index+1];
			
			if(child1 == nullptr) { 
				//　ﾊﾞｶｼﾞｬﾈｰﾉ
				return ;
			} else if(child1->number_of_key >= min_degree) {
				erase(child1, key);
			} else if(child0 != nullptr && child0->number_of_key >= min_degree){
				index--;
				
				for(int i = child1->number_of_key - 1; i >= 0; i--){
					child1->key[i+1] = child1->key[i];
				}
				for(int i = child1->number_of_key; i >= 0; i--){
					child1->children[i+1] = child1->children[i];
				}
				
				child1->key[0] = node->key[index];
				child1->children[0] = child0->children[child0->number_of_key];
				
				node->key[index] = child0->key[child0->number_of_key-1];
				
				child0->number_of_key--;
				child1->number_of_key++;
				
				erase(child1, key);
				
			} else if(child2 != nullptr && child2->number_of_key >= min_degree){
				
				child1->key[child1->number_of_key] = node->key[index];
				child1->children[child1->number_of_key + 1] = child2->children[0];
				
				node->key[index] = child2->key[0];
				
				for(int i = 0; i + 1 < child2->number_of_key; i++){
					child2->key[i] = child2->key[i+1];
				}
				for(int i = 0; i < child2->number_of_key; i++){
					child2->children[i] = child2->children[i+1];
				}
				
				child2->number_of_key--;
				child1->number_of_key++;
				
				operation(child2);
				erase(child1, key);
			} else if(child2 != nullptr || child0 != nullptr){
				Node* child_left, *child_right;
				
				if(child2 != nullptr){
					child_left = child1;
					child_right = child2;
					
				} else if(child0 != nullptr){
					child_left = child0;
					child_right = child1;
					
					index--;
				}
				
				child_left->key[min_degree - 1] = node->key[index];
					
				for(int i = min_degree; i < min_degree * 2 - 1; i++){
					child_left->key[i] = child_right->key[i - min_degree];
				}
				
				for(int i = min_degree; i < min_degree * 2; i++){
					child_left->children[i] = child_right->children[i - min_degree];
				}
				
				delete child_right;
				
				child_left->number_of_key = min_degree * 2 - 1;
				
				for(int i = index; i + 1 < node->number_of_key; i++){
					node->key[i] = node->key[i + 1];
				}
				
				for(int i = index + 1; i < node->number_of_key; i++){
					node->children[i] = node->children[i + 1];
				}
				
				node->number_of_key--;
				
				operation(node);
				erase(child_left, key);
			} else {
				
			}
		}
		
		
		operation(node);
	}
	
	const type operator[](int num) & {
		jnode j = nth_element(num);
		return j.node->key[j.index];
	}
};




#include<iostream>
 
int main(){
	using namespace std;
	
	BTree<int> bt(12);
	int Q;
	
	std::cin>>Q;
	
	for(int i = 0; i < Q; i++){
		int a, b, c;
		
		std::cin>>a>>b;
		
		if(a == 0){
			bt.insert(b);
			cout<<bt.size()<<endl;
		} else if(a == 1) {
			cout<<(bt.upper_bound(b) - bt.lower_bound(b))<<endl;
		} else if(a == 2){
			
			while(bt.search(b) != nullptr) {
				bt.erase(b);
			}
		} else if(a == 3) {
			BTree<int>::jnode jn;
			
			cin>>c;
			
			// int num = bt.lower_bound(b);
			
			// for(int i = num; i < bt.size() && bt[i] <= c; i++){
				// cout<<bt[i]<<endl;
			// }
			jn = bt.nth_element(bt.lower_bound(b));
			
			for(; jn.node != nullptr && jn.node->key[jn.index] <= c; jn++){
				cout<<jn.node->key[jn.index]<<endl;
			}
		} else if(a == 4) {
			
		}
	}
	
	return 0;
}