#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <deque>
#include <cstdio>

using namespace std;

const int INF = 2e9;

int main()
{
    freopen("input.txt", "r", stdin);
    int n, m, t;
    cin >> n >> m >> t;
    vector<vector<pair<int, char>>> g(n + 1);
    vector<pair<int, char>> obr(n + 1);
    for (int i = 2; i <= n; ++i) {
        int x;
        char c;
        cin >> x >> c;
        g[x].push_back({ i, c });
        obr[i].first = x;
        obr[i].second = c;
    }
    vector<vector<int>> heig;
    heig.reserve(1000);
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() == 0) {
            int h = 0;
            int now = i;
            while (now == 1) {
                now = obr[now].first;
                h++;
            }
            heig.resize(h + 1);
            heig[h].push_back(i);
        }
    }
    vector<pair<string, int>> mer(m);
    for (int i = 0; i < m; ++i) {
        int x;
        string s;
        cin >> x >> s;
        mer[i].first = s;
        mer[i].second = x;
    }
    sort(mer.begin(), mer.end());
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
    vector<int> start;
    for (int i = heig.size() - 1; i > 0; --i) {
        for (int l = 0; l < heig[i].size(); ++l) {
            start.push_back(heig[i][l]);
        }
        for (int j = 0; j < start.size(); ++j) {
            string s;
            int now = start[j];
            deque<int> d;
            for (int q = 0; q < i; ++q) {
                s = obr[now].second + s;
                d.push_front(now);
                now = obr[now].first;
            }
            d.push_front(now);
            auto it_1 = lower_bound(mer.begin(), mer.end(), s), it_2 = upper_bound(mer.begin(), mer.end(), s);
            it_2--;
            if (it_1 != mer.end() && it_1 == it_2) {
                for (int c = 0; c < d.size() - 1; ++c) {
                    for (int h = c + 1; h < d.size(); ++h) {
                        dp[d[c]][d[h]] = min(dp[d[c]][d[h]], (*it_1).second);
                    }
                }
            }
            while (d[0] != 1) {
                s.pop_back();
                s = obr[now].second + s;
                d.pop_back();
                now = obr[now].first;
                d.push_front(now);
                auto it_1 = lower_bound(mer.begin(), mer.end(), s), it_2 = upper_bound(mer.begin(), mer.end(), s);
                it_2--;
                if (it_1 != mer.end() && it_1 == it_2) {
                    for (int c = 0; c < d.size() - 1; ++c) {
                        for (int h = c + 1; h < d.size(); ++h) {
                            dp[d[c]][d[h]] = min(dp[d[c]][d[h]], (*it_1).second);
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i <= n; ++i) {
        for (int l = 0; l <= n; ++l) {
            cout << dp[i][l] << " ";
        }
        cout << "\n";
    }
    return 0;
}