#include <cstdio>

 #include <cstdlib>

 #include <string>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <sstream>

 #include <cctype>

 #include <vector>

 #include <map>

 #include <set>

 #include <iterator>

 #include <functional>

 #include <cmath>

 #include <numeric>

 #include <ctime>

 using namespace std;

 typedef long long LL;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define PB push_back

 #define MP make_pair

 #define SZ size()

 #define CL clear()

 #define AA first

 #define BB second

 #define EPS 1e-8

 #define ZERO(x) memset((x),0,sizeof(x))

 const int INF = ~0U>>;

 const double PI = acos(-1.0);

 int n,m,k;

 char in[];

 vector<PII> v[][];

 int tree[];

 char ch[];

 bool isAccepted(int sig){

     return sig>=n-m;

 }

 bool dfs(int rt,int sig){

 //    printf("rt = %d sig = %d\n",rt,sig);

     int rtVal = tree[rt];

     if( rtVal==- ){

         return isAccepted(sig);

     }

 //    printf("rtVal = %d\n",rtVal);

     bool res = false;

     for(int i=;i<v[sig][rtVal].SZ;i++){

         res = dfs(rt<<,v[sig][rtVal][i].AA);

         if(!res) continue;

         res &= dfs(rt<<|,v[sig][rtVal][i].BB);

         if( res ) break;

     }

     return res;

 }

 int main(){

     int kase = ;

     while( scanf("%d%d%d",&n,&m,&k)!=EOF ){

         getchar();

         for(int i=;i<;i++) for(int j=;j<;j++) v[i][j].CL;

         if( n==&&m==&&k== ) break;

         for(int i=;i<n;i++){

             for(int j=;j<k;j++){

                 gets(in);

                 istringstream sss(in);

                 int a,b;

                 while( sss>> a >> b ){

                     v[i][j].PB(MP(a,b));

 //                    printf("v[%d][%d].PB(%d,%d)\n",i,j,a,b);

                 }

             }

         }

 //        puts("*****");

         if( kase!= ) puts("");

         printf("NTA%d:\n",kase++);

         int q;

         while( true ){

             memset(tree,-,sizeof(tree));

             scanf("%d",&q);

             if( q==- ) break;

             for(int i=;i<=(<<(q+))-;i++){

                 scanf("%s",&ch);

                 if( strcmp(ch,"*")== ){

                     tree[i] = -;

                 } else {

                     tree[i] = ch[]-'a';

                 }

 //                printf("%d ",tree[i]);

             }//puts("");

             bool ok = dfs(,);

             if(ok) puts("Valid");

             else puts("Invalid");

         }

     }

     return ;

 }