Trie

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
struct Trie
{
    struct node
    {
        int num; // Số từ đi qua nút đó
        int index; // Địa chỉ
        int w_count; // Số từ kết thúc tại đây
        int child[26]; // các nút con
    };
    vector<node> Tree;
    void new_node()
    {
        node tmp;
        tmp.num = 0;
        tmp.w_count = 0;
        tmp.index = Tree.size();
        for (int i = 0; i < 26; ++ i)
        {
            tmp.child[i] = -1;
        }
        Tree.push_back(tmp);
    }
    void add_word(const string &s)
    {
        int id = 0;
        for (int i = 0; i < s.length(); ++ i)
        {
            ++Tree[id].num;
            int w = s[i] - 'a';
            if (Tree[id].child[w] == -1)
            {
                new_node();
                Tree[id].child[w] = Tree.size() - 1;
            }
            id = Tree[id].child[w];
        }
        ++Tree[id].num;
        ++Tree[id].w_count;
    }
    int Index(const string & s)
    {
        int id = 0;
        for (int i = 0; i < s.length(); ++ i)
        {
            int w = s[i] - 'a';
            if(Tree[id].child[w] == -1)
            {
                return -1;
            }
            id = Tree[id].child[w];
        }
        return id;
    }
};
Trie Test;
string s;
int n;
void read()
{
   Test.new_node();
   cin >> n;
   for (int i = 1; i <= n; ++ i)
   {
       cin >> s;
       Test.add_word(s);
       cout << Test.Index(s) << '\n';
   }
}
void solve()
{

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen(TASK".INP", "r", stdin);
    //freopen(TASK".OUT", "w", stdout);
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        read();
        solve();
    }
}