#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T>
struct int_it : iterator<random_access_iterator_tag, T, T, T*, T&>{
    T x = 0;
    int_it(){}
    int_it(const int_it&& rhs): x(rhs.x){}
    int_it(const int_it<T>& rhs): x(rhs.x){}
    int_it(const T& y): x(y){}
    int_it& operator=(const int_it rhs){ x = rhs.x; return *this; }
    const T& operator*()const{ return x; }
    bool operator==(const int_it rhs)const{ return x == rhs.x; }
    bool operator!=(const int_it rhs)const{ return x != rhs.x; }
    const T* operator->(){ return &x; }
    int_it& operator++(){ ++x; return *this; }
    int_it operator++(int){ int_it tmp = *this; ++x; return tmp; }
    int_it& operator--(){ --x; return *this; }
    int_it operator--(int){ int_it tmp = *this; --x; return tmp; }
    int_it& operator+=(const T& y){ x += y; return *this; }
    int_it& operator-=(const T& y){ x += y; return *this; }
    int_it operator+(const T& x)const{ int_it tmp = *this; tmp += x; return tmp; }
    int_it operator-(const T& x)const{ int_it tmp = *this; tmp -= x; return tmp; }
    T operator-(const int_it rhs)const{ return x - rhs.x; }
    const T& operator[](const T y)const{ return x + y; }
    bool operator<(const int_it& rhs)const{ return x < rhs.x; }
    bool operator>(const int_it& rhs)const{ return x > rhs.x; }
    bool operator<=(const int_it& rhs)const{ return x <= rhs.x; }
    bool operator>=(const int_it& rhs)const{ return x >= rhs.x; } };

template <typename T>
void swap(int_it<T> a, int_it<T> b){
    swap(a.x, b.x); }

trie<string, int, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>
    t;

int main(){
    ifstream f("trie.in");
    ofstream g("trie.out");
    int x;
    string str;
    while(f >> x >> str){
        if(x == 0) ++t[str];
        else if(x == 1){
            if(--t[str] == 0)
                t.erase(str); }
        else if(x == 2)
            g << t[str] << '\n';
        else if(x == 3)
            g << *partition_point(int_it<int>(0), int_it<int>(str.size()+1),
                [&](const int y){
                    auto tmp = t.prefix_range(begin(str), begin(str)+y);
                    return tmp.first != tmp.second; })-1 << '\n'; }
    return 0; }