#include <iostream>
#include <string.h>
#include <list>
using namespace std;
class nodo{
      public:
      char pa;
      int sig;
      nodo(int p,char x){pa=x;sig=p;}
};
char Sirve(string cadena,list<nodo>norma[],int Ter[],int N){
      int i=1;int d;int j=0;list<nodo>::iterator it;
     while(j<cadena.size()){
                d=1;                 
                for(it=norma[i].begin();  it !=norma[i].end(); ++it)
                     if(cadena[j]==(it->pa)){i=it->sig;j++;d=0;break;}
                     if(d==1)return 'N';                 
                            }
     if(Ter[i]!=1)return 'N'; 
     return 'Y';
}   
int main(){
    int Caso; 
    scanf("%d",&Caso);
    while(Caso--){string x;int N,F,M,S;                                     // N= Numero de Estado de maquina , F El numero de E.Finales
                  scanf("%d %d %d %d",&N,&F,&M,&S); //  M= el numero de simbolos no terminales, S, Numero de cadenas
                  int Ter[N+1];int p;list<nodo>norm[N+1];
                  for(int i=0;i<N;i++){Ter[i]=0;}
                  while(F--){
                      scanf("%d",&p);
                      Ter[p]=1;}p=M*N;
                  while(p--){int i,j;char r;
                      scanf("%d %d %s",&i,&j,&r); 
                      //leo      
                      norm[i].push_back(nodo(j,r));
                             }
                  while(S--){
                      cin>>x;
                      printf("%c\n",Sirve(x,norm,Ter,N));
                             }
                  }
    return 0;
    }