struct Trie
{
    struct Node
    {
        int cnt;
        int suf;
        vi go;
        Node() { cnt = 0, suf = 0, go.assign(26, -1); };
    };
    vector<Node> t;
    Trie() { t.inb(Node()); };
    int adds(string s)
    {
        int u = 0;
        for (int i = 0; i < (int)s.size(); ++i)
        {
            if (t[u].go[s[i] - 'a'] == -1)
            {
                t[u].go[s[i] - 'a'] = t.size();
                t.inb(Node());
            }
            u = t[u].go[s[i] - 'a'];
        }
        return u;
    }
    void buildAK()
    {
        queue<int> q;
        q.push(0);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i)
            {
                int to = 0;
                if (u)
                    to = t[t[u].suf].go[i];
                if (t[u].go[i] != -1)
                {
                    t[t[u].go[i]].suf = to;
                    q.push(t[u].go[i]);
                }
                else
                {
                    t[u].go[i] = to;
                }
            }
        }
    }
};