#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,maxk=21,mod=998244353;

int dp[maxn][maxk][maxk];
int len[maxn],tdp[maxn],sum[maxk];
string s[maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,K,a;
    cin>>n>>K>>a;
    auto mislen=[&](string &s) -> void
    {
        if(s.length()<=2*K) return;
        string tmp;
        for(int i=0;i<K;++i)
            tmp.push_back(s[i]);
        for(int i=s.length()-K;i<s.length();++i)
            tmp.push_back(s[i]);
        s=tmp;
    };
    auto addmod=[&](int x,int y) -> int
    {
        x+=y;
        return x>=mod?x-mod:x;
    };
    for(int o=1;o<=n;++o)
    {
        cin>>s[o];
        len[o]=s[o].size();
        for(int i=1;i<=K&&i<=len[o];++i)
        {
            tdp[i-1]=0;
            tdp[i]=(s[o][i-1]=='O');
            if(len[o]-i+1<=K) dp[o][i][len[o]-i+1]=tdp[i];
            for(int j=i+1;j<=len[o];++j)
            {
                tdp[j]=0;
                if(s[o][j-1]=='O') tdp[j]=addmod(tdp[j-1],mod-tdp[max(i,j-K)-1]);
                if(len[o]-j+1<=K) dp[o][i][len[o]-j+1]=tdp[j];
                tdp[j]=addmod(tdp[j-1],tdp[j]);
            }
        }
        mislen(s[o]);
        len[o]=s[o].length();
        cout<<dp[o][1][1]<<' ';
    }
    for(int o=n+1;o<=n+a;++o)
    {
        int o1,o2;
        cin>>o1>>o2;
        s[o]=s[o1]+s[o2];
        mislen(s[o]);
        len[o]=s[o].length();
        for(int i=1;i<=K&&i<=len[o];++i)
            for(int j=1;j<=K&&len[o]-j+1>=i;++j)
            {
                if(s[o][i-1]=='~'||s[o][len[o]-j]=='~') continue;
                if(j>len[o2]) dp[o][i][j]=dp[o1][i][j-len[o2]];
                else if(i>len[o1]) dp[o][i][j]=dp[o2][i-len[o1]][j];
                else
                {
                    for(int l=1;l<=K&&l<=len[o2]-j+1;++l)
                        sum[l]=addmod(sum[l-1],dp[o2][l][j]);
                    for(int l=1;l<=K&&i<=len[o1]-l+1;++l)
                    {
                        if(s[o1][len[o1]-l]=='O')
                            dp[o][i][j]=addmod(dp[o][i][j],1ll*dp[o1][i][l]*sum[min(K-l+1,len[o2]-j+1)]%mod);
                    }
                }
            }
        cout<<dp[o][1][1]<<' ';
    }
}