#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAX_N = 2e5+10;
const int INF = 2e18;
const int MOD = 998244353;

// declare
int n, k, q;
string tmp;
vector<pair<string, string>> v;

struct Matrix{
    int n, m;
    vector<vector<int>> arr;

    Matrix(int _n = 0, int _m = 0){
        n = _n;
        m = _m;
        arr.assign(n, vector<int>(m));
    }

    vector<int> & operator [] (int i){
        return arr[i];
    }

    Matrix operator * (Matrix b){
        Matrix ret(n, b.m);
        // assert(m==b.n);
        for (int i=0 ; i<n ; i++){
            for (int j=0 ; j<b.m ; j++){
                for (int k=0 ; k<m ; k++){
                    ret.arr[i][j] += arr[i][k]*b.arr[k][j]%MOD;
                    ret.arr[i][j] %= MOD;
                }
            }
        }
        return ret;
    }

    void print(){
        for (int i=0 ; i<n ; i++){
            for (int j=0 ; j<m ; j++){
                cerr << arr[i][j] << " ";
            }
            cerr << "\n";
        }
        cerr << "\n";
    }
};

pair<string, string> get_prefix_and_suffix(string &s){
    pair<string, string> ret;
    ret.first = tmp.substr(0, k);
    if (tmp.size()<=k) ret.second = tmp;
    else ret.second = tmp.substr(tmp.size()-k);
    return ret;
}

Matrix convert(string &s){
    int h = min((int)s.size(), k);

    Matrix ret(h, h);
    for (int i=0 ; i<h ; i++){ // 枚舉從誰開始
        vector<int> dp(s.size()+100);
        if (s[i]=='~') continue;
        dp[i] = 1;

        for (int j=i+1 ; j<s.size() ; j++){ // 枚舉其他人
            for (int p=1 ; p<=k ; p++){ // 枚舉要走幾步轉移
                if (s[j]=='O' && j-p>=0 && s[j-p]=='O'){
                    dp[j] = (dp[j]+dp[j-p])%MOD;
                }
            }
        }
        for (int p=0 ; p<h ; p++){
            ret[i][p] = dp[(int)s.size()-h+p];
        }
    }

    return ret;
}

Matrix convert_mid(int idx1, int idx2){
    int n = v[idx1].second.size();
    int m = v[idx2].first.size();
    Matrix ret(n, m);
    for (int i=0 ; i<n ; i++){
        for (int j=0 ; j<m ; j++){
            if (v[idx1].second[i]=='O' && v[idx2].first[j]=='O'){
                int dis = (n-i)+j;
                if (dis<=k){
                    ret[i][j] = 1;
                }
            }
        }
    }

    return ret;
}

vector<Matrix> m;

vector<int> len;
vector<string> strings;

void solve(){

    // input
    cin >> n >> k >> q;
    v.resize(n+1);
    m.resize(n+1);
    len.resize(n+1);
    strings.resize(n + 1);
    for (int i=1 ; i<=n ; i++){
        cin >> tmp;
        v[i] = get_prefix_and_suffix(tmp);
        m[i] = convert(tmp);

        len[i] = min((int)tmp.size(), k);
        if (len[i] <k) strings[i] = tmp;
    }

    // for (int i=1 ; i<=n ; i++){
    //     cerr << "i=" << i << "\n";
    //     m[i].print();
    // }
    // cerr << "\n";

    // queries
    for (int i=0 ; i<q ; i++){
        int x, y;
        cin >> x >> y;
        len.push_back(min(k, len[x] + len[y]));
        pair<string, string> xx = v[x], yy = v[y];
        pair<string, string> p;
        if (xx.first.size()+yy.first.size()<=k){
            p.first = xx.first+yy.first;
            p.second = xx.second+yy.second;
        }
        else {
            p.first = xx.first;
            p.second = yy.second;
            int ptr = 0;
            while (ptr < yy.first.size() and p.first.size() < k) {
                p.first.push_back(yy.first[ptr++]);
            }

            ptr = xx.second.size() - 1;
            while (ptr >= 0 and p.second.size() < k) {
                p.second.insert(p.second.begin(), xx.second[ptr--]);
            }
        }
        v.push_back(p);
        if (len.back() < k) strings.push_back(p.first);
        else strings.push_back("");

        if (len[x] +len[y]<k){
            m.push_back(convert(p.first));
        }
        else if (len[x] < k or len[y] <k) {
            auto r = m[x] * convert_mid(x, y) * m[y];
            if (r.m < m[x].m) {
                // m[x] no right (k - r.m)
                Matrix asdad(m[x].n, m[x].m);
                for (int i = 0; i <m[x].n; i++) {
                    for (int j = 0; j <m[x].m; j++) {
                        int t = m[x].m - r.m;
                        asdad[i][j] = j < t ? m[x][i][m[x].m - t + j] : r[i][j - t];
                    }
                }
                r = asdad;
            }
            if (r.n < m[y].n) {
                Matrix asdad(m[y].n, m[y].m);
                for (int i = 0; i <m[y].n; i++) {
                    for (int j = 0; j <m[y].m; j++) {
                        int t = m[y].n - r.n;
                        asdad[i][j] = i < r.n ? r[i][j] : m[y][i - r.n][j];
                    }
                }
                r = asdad;
            }
            m.push_back(r);
        }
        else{
            m.push_back(m[x]*convert_mid(x, y)*m[y]);
        }
        assert(m.back().n == m.back().m and m.back().n == len.back());
        // cout <<"--------------------------\n";
        // cout <<"i,x,y=" << i << ' ' <<x <<' '<<y <<'\n';
        // m.back().print();
        // cerr << v[x].second << " " << v[y].first << "\n";
        // convert_mid(x,y).print();

    }

    // preview
    // cerr << "============== m =============\n";
    // for (int i=1 ; i<m.size() ; i++){
    //     m[i].print();
    // }
    // cerr << "\n";
    // cerr << "============== v =============\n";
    // for (int i=1 ; i<v.size() ; i++){
    //     cerr << v[i].first << " " << v[i].second << "\n";
    // }
    // cerr << "\n";

    // output
    for (int i=1 ; i<v.size() ; i++){
        int n = m[i][0].size();
        cout << m[i][0][n-1] << " ";
    }
    cout << "\n";
    
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    int t = 1;
    while (t--){
        solve();
    }
    
    return 0;
}