Aho Corasick

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
struct aho_corasick
{
    struct node
    {
        int nxt[26], go[26], link, val;
        node()
        {
            memset(nxt, -1, sizeof(nxt));
            memset(go, 0, sizeof(nxt));
            link = val = 0;
        }
    };
    vector<node> tree;
    void new_node()
    {
        node tmp;
        tree.push_back(tmp);
    }
    void reset()
    {
        tree.clear();
        new_node();
    }
    void add(string &s, int val)
    {
        int id = 0;
        for (char &c : s)
        {
            int w = c - 'a';
            if (tree[id].nxt[w] == -1)
            {
                tree[id].nxt[w] = tree.size();
                new_node();
            }
            id = tree[id].nxt[w];
        }
        tree[id].val += val;
    }
    void build()
    {
        queue<int> q;
        q.push(0);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            tree[u].val += tree[tree[u].link].val;
            for (int w = 0; w < 26; ++ w)
            {
                int v = tree[u].nxt[w];
                if (v != -1)
                {
                    tree[u].go[w] = v;
                    if (u != 0)
                    {
                        tree[v].link = tree[tree[u].link].go[w];
                    }
                    else
                    {
                        tree[v].link = 0;
                    }
                    q.push(v);
                }
                else
                {
                    tree[u].go[w] = tree[tree[u].link].go[w];
                }
            }
        }
    }
    long long get(string s)
    {
        long long ret = 0;
        int u = 0;
        for (char &c : s)
        {
            u = tree[u].go[c - 'a'];
            ret += tree[u].val;
        }
        return ret;
    }
} tree;
string a, b;
void read()
{
    tree.reset();
    cin >> a >> b;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        string s;
        int val;
        cin >> s >> val;
        tree.add(s, val);
    }
    tree.build();
}
void solve()
{

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