HA34

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>

using namespace std;

class TrieNode {
public:
    array<int, 26> children;
    int best_popularity;
    int best_index;

    TrieNode() : best_popularity(-1), best_index(-1) {
        children.fill(-1);
    }
};

class Trie {
private:
    vector<TrieNode> nodes;

public:
    Trie() {
        nodes.reserve(1000000);
        // Начинаем с одного корня
        nodes.push_back(TrieNode());
    }

    void updateRootIfBetter(int popularity, int index) {
        // Обновляем корень
        if (popularity > nodes[0].best_popularity) {
            nodes[0].best_popularity = popularity;
            nodes[0].best_index = index;
        }
    }

    void insertWord(const string &word, int popularity, int index) {
        int cur = 0;
        for (char c : word) {
            int nxt = c - 'a';
            if (nodes[cur].children[nxt] == -1) {
                nodes[cur].children[nxt] = (int)nodes.size();
                nodes.push_back(TrieNode());
            }
            cur = nodes[cur].children[nxt];
            // Обовляем лучший
            if (popularity > nodes[cur].best_popularity) {
                nodes[cur].best_popularity = popularity;
                nodes[cur].best_index = index;
            }
        }
    }

    int getChild(int node, char c) const {
        if (node == -1) return -1;
        return nodes[node].children[c - 'a'];
    }

    int getBestIndex(int node) const {
        if (node == -1) return -1;
        return nodes[node].best_index;
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;

    vector<string> words(N);
    vector<int> popularity(N);
    for (int i = 0; i < N; i++) {
        cin >> words[i] >> popularity[i];
    }

    Trie trie;

    for (int i = 0; i < N; i++) {
        trie.updateRootIfBetter(popularity[i], i + 1);
    }

    for (int i = 0; i < N; i++) {
        trie.insertWord(words[i], popularity[i], i + 1);
    }

    vector<int> prefix_stack;
    prefix_stack.reserve(Q + 1);
    prefix_stack.push_back(0);

    for (int i = 0; i < Q; i++) {
        char op; cin >> op;
        if (op == '+') {
            char c; cin >> c;
            int top_node = prefix_stack.back();
            int nxt = trie.getChild(top_node, c);
            prefix_stack.push_back(nxt);
        } else {
            prefix_stack.pop_back();
        }

        int cur_node = prefix_stack.back();
        int ans = trie.getBestIndex(cur_node);
        cout << ans << "\n";
    }

    return 0;
}