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 <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <math.h>
#include <string.h>
#include <time.h>
#include <vector>

using namespace std;

template <typename T>
class node
{
public:
    T data;
    node<T> *left = NULL;
    node<T> *right = NULL;
    int balance = 0;
    node(T data)
    {
        this->data = data;
    };

    // you can implement other relevant things here
    // TODO
    int depth = 1;
};
template <typename T>
class AVLtree
{
    node<T> *root = NULL;

    /// you can implement other relevant things here
    /// TODO
    int N = 0;
    int Depth(node<T>* &root) {
        return root->depth;
    }
    int GetBalance(node<T>* &root) {
        int depth_Left, depth_Right;
        if (!root->left) depth_Left = 0;
        else depth_Left = root->left->depth;
        if (!root->right) depth_Right = 0;
        else depth_Right = root->right->depth;
        return depth_Left - depth_Right;
    }
    int update_depth(node<T>* &root) {
        int depth_root, depth_Left, depth_Right;
        if (!root->left) depth_Left = 0;
        else depth_Left = root->left->depth;
        if (!root->right) depth_Right = 0;
        else depth_Right = root->right->depth;
        depth_root = (depth_Left > depth_Right ? depth_Left : depth_Right) + 1;
        return root->depth = depth_root;
    }
    node<T>* rotLeft(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->right;
        y->right = x->left;
        x->left = y;
        update_depth(y);
        update_depth(x);
        return x;
    }
    node<T>* rotRight(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->left;
        y->left = x->right;
        x->right = y;
        update_depth(y);
        update_depth(x);
        return x;
    }
    node<T>* rotLeftRight(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->left;
        node<T>* z = x->right;
        x->right = z->left;
        z->left = x;

        y->left = z->right;
        z->right = y;
        update_depth(y);
        update_depth(x);
        update_depth(z);
        return z;
//        root->left = rotLeft(root->left);
//        return rotRight(root);
    }
    node<T>* rotRightLeft(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->right;
        node<T>* z = x->left;
        x->left = z->right;
        z->right = x;

        y->right = z->left;
        z->left = y;
        update_depth(y);
        update_depth(x);
        update_depth(z);
        return z;
//        root->right = rotRight(root->right);
//        return rotLeft(root);
    }
    node<T>* add(node<T>* &root, T &data) {
        if (root == NULL) {
            node<T>* Node = new node<T>(data);
            return Node;
        }
        else {
            if (data >= root->data) {
                root->right = add(root->right, data);
            }
            else {
                root->left = add(root->left, data);
            }
            update_depth(root);
            int balance = GetBalance(root);
            if (balance > 1) {
                if (GetBalance(root->left) >= 0) root = rotRight(root);
                else root = rotLeftRight(root);
            }
            if (balance < -1) {
                if (GetBalance(root->right) <= 0) root = rotLeft(root);
                else root = rotRightLeft(root);
            }
            return root;
        }
    }
    node<T>* find_max(node<T>* &root) {
        if (root == NULL) return NULL;
        if (root->right == NULL) return root;
        return find_max(root->right);
    }
    node<T>* find_min(node<T>* &root) {
        if (root == NULL) return NULL;
        if (root->left == NULL) return root;
        return find_min(root->left);
    }
    node<T>* find_value(node<T>* &root, T &data) {
        if (root == NULL) return NULL;
        if (root->data == data) return root;
        if (data < root->data) return find_value(root->left, data);
        return find_value(root->right, data);
    }
    node<T>* remove(node<T>* &root, T &data){
        if (root == NULL) return NULL;
        if (data < root->data) root->left = remove(root->left, data);
        else {
            if (data > root->data) root->right = remove(root->right, data);
            else {
                if (root->left == NULL && root->right == NULL) {
                    delete root;
                    root = NULL;
                    return NULL;
                }
                if (root->left == NULL) return root->right;
                if (root->right == NULL) return root->left;
                node<T> *y = find_min(root->right);
                root->data = y->data;
                root->right = remove(root->right, root->data);
            }
        }
        update_depth(root);
        int D = Depth(root);
        int Balance = GetBalance(root);
        if (Balance > 1 && GetBalance(root->left) >= 0) return rotRight(root);
        if (Balance > 1 && GetBalance(root->left) < 0) return rotLeftRight(root);
        if (Balance < -1 && GetBalance(root->right) <= 0) return rotLeft(root);
        if (Balance < -1 && GetBalance(root->right) > 0) return rotRightLeft(root);
        return root;
    }
    node<T>* lower_bound(node<T>* &root, T &data) {
        if (root == NULL) return NULL;
        if (root->data < data) return lower_bound(root->right, data);
        node<T> *Res = lower_bound(root->left, data);
        if (Res != NULL) return Res;
        return root;
    }
    node<T>* upper_bound(node<T>* &root, T &data) {
        if (root == NULL) return NULL;
        if (root->data > data) return upper_bound(root->left, data);
        node<T> *Res = upper_bound(root->right, data);
        if (Res != NULL) return Res;
        return root;
    }
    void print(node<T> *&subroot)
    {
        if (subroot == 0)
        {
            cout << '*';
            return;
        }
        cout << subroot->data;
        cout << '(';
        print(subroot->left);
        cout << '|';
        print(subroot->right);
        cout << ')';
        return;
    }
    void PrintLNR(node<T>* &root) {
        if (root == 0) return;
        PrintLNR(root->left);
        cout << root->data << ' ';
        PrintLNR(root->right);
    }

public:
    AVLtree() {}

    // the add function:
    int size() {
        return N;
    }
    bool empty() {
        return root == NULL;
    }
    bool add(T &data)
    {
        ///if (find_value(root, data) == NULL)
        root = add(root, data);
        N++;
        return true;
    }
    bool find(T &data) {
        return find_value(root, data) != NULL;
    }
    bool remove(T &data) {
        if (find_value(root, data) == NULL) return false;
        N--;
        root = remove(root, data);
        return true;
    }
    bool DoLower_bound(T &data, T &Value) {
        node<T>* Res = lower_bound(root, data);
        if (Res == NULL) {
            return false;
        }
        Value = Res->data;
        return true;
    }
    bool DoUpper_bound(T &data, T &Value) {
        node<T>* Res = upper_bound(root, data);
        if (Res == NULL) {
            return false;
        }
        Value = Res->data;
        return true;
    }
    T find_min() {
        return find_min(root)->data;
    }
    T find_max() {
        return find_max(root)->data;
    }
    void print()
    {
        ///print(root);
        PrintLNR(root);
    }
};

#define INP "solve"
#define OUT "solve"
int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    ///freopen(INP ".inp","r",stdin);
    ///freopen(OUT ".out","w",stdout);
	AVLtree<int> ATree;
	int Q;
	cin >> Q;
	while (Q--) {
        int Type;
        cin >> Type;
        if (Type == 0) {
            int x;
            cin >> x;
            ATree.add(x);
            cout << ATree.size() << '\n';
        }
        if (Type == 1) {
            int x;
            cin >> x;
            vector <int> A;
            while (ATree.find(x)) {
                A.push_back(x);
                ATree.remove(x);
            }
            cout << (int)A.size() << '\n';
            for (int x : A) ATree.add(x);
        }
        if (Type == 2) {
            int x;
            cin >> x;
            while (ATree.find(x)) ATree.remove(x);
        }
        if (Type == 3) {
            int L, R;
            cin >> L >> R;
            vector <int> A;
            if (ATree.DoLower_bound(L, L) == true) {
                while (L <= R) {
                    A.push_back(L);
                    ATree.remove(L);
                    if (ATree.DoLower_bound(L, L) == false) break;
                }
            }
            for (int x : A) {
                cout << x << '\n';
                ATree.add(x);
            }
        }
	}

//    while (true) {
//        int Type;
//        cin >> Type;
//        if (Type == 0) break;
//        if (Type == 1) {
//            int x;
//            cin >> x;
//            ATree.add(x);
//            continue;
//        }
//        if (Type == 2) {
//            int x;
//            cin >> x;
//            ATree.remove(x);
//            continue;
//        }
//        if (ATree.empty()) {
//            if (Type > 4) {
//                int x;
//                cin >> x;
//            }
//            cout << "empty" << '\n';
//            continue;
//        }
//        if (Type == 3) {
//            cout << ATree.find_min() << '\n';
//            continue;
//        }
//        if (Type == 4) {
//            cout << ATree.find_max() << '\n';
//            continue;
//        }
//        int x;
//        cin >> x;
//        int Res = -1;
//        if (Type == 5) x++;
//        if (Type <= 6) {
//            if (ATree.DoLower_bound(x, Res)) cout << Res << '\n';
//            else cout << "no" << '\n';
//            continue;
//        }
//        if (Type == 7) x--;
//        if (ATree.DoUpper_bound(x, Res)) cout << Res << '\n';
//        else cout << "no" << '\n';
//    }
    ///ATree.print();
}