Trie

#include <iostream>
#include <string>
#include <map>
#include <algorithm>


struct Node {
    std::string key;
    Node* desc[5];

    Node (std::string s): key (s) {
        for (int i = 0; i < 5; ++ i)
            desc[i] = nullptr;
    }
};

int n, m, task, dim;
std::string s ("ROOT"), temp;
Node* Root = new Node (s);
std::map <std::string, bool> Hash;


inline void Insert (Node*& root, std::string s, std::string temp) {
    if (!s.empty ()) {
        if (!root) root = new Node (temp);
        std::cout << root->key << " ";
        temp += s.back ();
        char aux = s.back (); s.pop_back ();
         Insert (root->desc[aux - '0'], s, temp);
    } else root = new Node (temp), std::cout << root->key << " ";
}

inline bool hasMoreSons (Node*& root) {
    return root->desc[1] || root->desc[2] || root->desc[3] ||root->desc[4];
}

inline void Delete (Node*& root, std::string s) {
    std::cout << root->key << " ";
    if (!s.empty ()) {
        char aux = s.back (); s.pop_back ();
        //std::cout << root->key << " ";
        if (root->desc[aux - '0']) Delete (root->desc[aux - '0'], s);
        if (!hasMoreSons (root) && root->key != "ROOT") delete root;
    } else delete root;
}

inline int Search (Node*& root, std::string s, std::string temp) {
    //std::cout << root->key << " ";
    if (hasMoreSons (root)) {
        temp += s.back ();
        std::cout << root->key << " ";
        char aux = s.back (); s.pop_back ();
         if (root->desc[aux - '0']) return Search (root->desc[aux - '0'], s, temp);
         else return dim >> (2 * (int)temp.size ());
     } else return dim;
}

inline void R1234 (Node*& root) {
    if (root) {
        std::cout << root->key << " ";
        for (int i = 1; i <= 4; ++ i)
            R1234 (root->desc[i]);
    }
}


int main () {
    std::cin >> n >> m;
    dim = 1 << (2 * __builtin_ctz (n));
    for (int i = 1; i <= m; ++ i) {
        std::cin >> task >> s;
        if (task == 1) {
            std::reverse (s.begin (), s.end ());
            if (Hash[s]) Delete (Root, s);
            else Insert (Root, s, temp);
            std::cout << "\n";
            std::reverse (s.begin (), s.end ());
            Hash[s] = !Hash[s];
            //std::cout << Root->key << "\n";
            //R1234 (root); std::cout << "\n";
        } else {
            if (Hash[s]) std::cout << "0\n";
            else std::reverse (s.begin (), s.end ()), std::cout << Search (Root, s, temp) << "\n";
        }
    }

    return 0;
}