struct Node{
    int next[26];
    int term;
    Node(){
        term = -1;
        for (int i = 0; i < 26; i++)
            next[i] = -1;
    }
};

vector <Node> trie;

int root = 0;

void add(string & s, int id){
    int cur = root;
    for (int i = 0; i < s.length(); i++){
        int c = s[i] - 'a';
        if (trie[cur].next[c] == -1){
            trie[cur].next[c] = trie.size();
            trie.push_back(Node());
        }
        cur = trie[cur].next[c];
    }
    trie[cur].term = id;
}