#include <iostream>
#include <map>
#include <vector>
#include <fstream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;


typedef vector<map<char,vector<int> > > GRAF;

ifstream fin("nfa.in");
ofstream fout("nfa.out");

void adauga_arc(GRAF &graf, int q1, int q2, char c) {
    /// adauga nodului de start(q1) faptul ca litera "c" il trimite in nodul end(q2) //
    graf[q1][c].push_back(q2);
}

void afiseaza_graf(GRAF graf, int nr_stari) {
    ///itereaza prin noduri
    for(int i=0;i<=nr_stari;i++) {
        /// ia map-ul asociat nodului si itereaza-i prin chei
        cout<<"pentru "<<i<<"::\n";
        for(auto mp = graf[i].begin(); mp!= graf[i].end();++mp) {
            cout<<mp->first<<":{ ";
            //pentru fiecare cheie, iterez prin elem. din vectorul lui
            for(auto ends=mp->second.begin();ends!=mp->second.end();++ends) {
                cout<<*ends<<" ";
            }
            cout<<"}\n";

        }
    }
}

/**
 * Functie recursiva care traverseaza graful
 * word: cuvantul in sine
 * nod_curent: nodul la care a ajuns functia
 * i_char_curent: indicele caracterului la care a ajuns functia
 * i_char_final: indicele caracterului final
 * graf: graful automatului
 * stari_finale: vectorul de stari finale
 * */
int is_valid=0;
void verify(string& word, int nod_curent, int i_char_curent, const int i_char_final, GRAF& graf, int current_lg, vector<int>& stari_finale, vector<vector<bool>>& matrice_vizitati) {
    ///daca nu s-a mai ajuns aici cu lungimea asta, mergi pe aici///
	if(matrice_vizitati[nod_curent][current_lg] == false && is_valid == 0) {

        ///Daca am ajuns intr-un nod marcat ca nod final si la ultimul caracter din cuvant=> cuvant acceptat de automat
        if( i_char_curent == i_char_final )
            if(find(stari_finale.begin(), stari_finale.end(), nod_curent) != stari_finale.end())
            {
            	is_valid=1;
            }


        /// Verifica de unde poti pleca din nodul nod_curent cu caracterul word[i_char_curent] ///
        /// itereaza prin vectorul dat de graf[nod_curent][word[i_char_curent]] si reapeleaza functia cu caracterul urmator ///
        char c = word[i_char_curent];
            for(auto &ends : graf[nod_curent][c]) {
                if(matrice_vizitati[ends][current_lg+1] == false){
                    matrice_vizitati[ends][current_lg] = true;
                    verify(word, ends,i_char_curent+1, i_char_final, graf,current_lg+1, stari_finale, matrice_vizitati);

                }

            }
    }
}

bool is_accepting_state(int nod, vector<int>& stari_finale){
    return find(stari_finale.begin(), stari_finale.end(),nod)!=stari_finale.end();
}


int main()
{
    vector<int>stari_finale;
    vector<vector<bool>> matrice_vizitati;
    int nr_stari, nr_tranzitii, stare_initiala, nr_stari_finale;
    int choice=-1;
    bool status;
    GRAF graf;
    /* Varianta "automata" ---- pentru testat pe InfoArena */
    fin>>nr_stari>>nr_tranzitii>>nr_stari_finale>>stare_initiala;
    stari_finale.resize(nr_stari_finale);
    int x=0;

    for(int i=0;i<nr_stari_finale;i++){
        fin>>x;
        stari_finale.push_back(x);
    }
    graf.resize(nr_stari+1);
    for(int i=0;i<nr_tranzitii;i++) {
            int q1, q2; char c;
            fin>>q1>>q2>>c;
            adauga_arc(graf, q1,q2,c);
        }
    fin>>x; string word;

    for(int i=0;i<x;i++) {
        fin>>word;
        is_valid=0;
        matrice_vizitati.resize(nr_stari+1);
        for(vector<bool> &v:matrice_vizitati) {
            v.resize(word.length()+1);
            for (auto&& x:v)
                x=false;
            }

        verify(word,stare_initiala,0,word.length(),graf,0,stari_finale,matrice_vizitati);

        if(is_valid)
            fout<<"1\n";
            else
            fout<<"0\n";

    }

}