#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
#include<queue>


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


int main(){
    int N, M, K, S; // numarul de stari
    fin>>N>>M>>K;
    fin>>S;
    std::vector<int> stariFinale; // multimea de stari finale
    for(int i = 0; i<K; i++){
        int x;
        fin>>x;
        stariFinale.push_back(x);
    }
    

    std::unordered_map<std::string, std::vector<std::pair<int, char>>> tranzitii;  
    // asemanator cu o lista de adiacenta, dar cu perechi de forma {vecin, litera}
    // Ex: tranzitii["1"] ={{2,a},{3,a},{2,b}} - din starea 1 putem sa mergem in starea 2 cu litera a sau b, in starea 3 cu litera a...
    for(int i = 0; i<M; i++){
        int x, y;
        char l;
        fin>>x>>y>>l;
        tranzitii[std::to_string(x)].push_back({y,l});
    }
        
        
    

    
    int nrCuv; // numarul de cuvinte de verificat
    fin>>nrCuv;
    std::vector<std::string> Cuvinte; // cuvintele de verificat
    for(int i =0; i< nrCuv; i++){
        std::string cuvant;
        fin>>cuvant;
        Cuvinte.push_back(cuvant);
    }

   // parcurgere cuvinte
   for(std::string cuvant: Cuvinte){
    std::queue<int> coada; // coada de stari pentru fiecare cuvant
    coada.push(S);
    bool acceptat = false;

    for(int i=0; i<cuvant.length();i++){
        std::queue<int> stariAdiacente; // coada de stari pentru fiecare litera din cuvant

        while(!coada.empty()){
            int stare = coada.front();
            coada.pop();

            for(auto vecin : tranzitii[std::to_string(stare)]){
                if(vecin.second == cuvant[i]){
                    stariAdiacente.push(vecin.first);
                }
            }
        }
        coada = stariAdiacente;
    }


    // verificare stari finale
    while(!coada.empty()){
        int stareCurenta = coada.front();
        coada.pop();

        if(std::find(stariFinale.begin(), stariFinale.end(),stareCurenta) != stariFinale.end()){
            acceptat = true; // trebuie ca cel putin una sa fie stare finala
            break;
        }
    }

    if(acceptat){
        fout<<1<<"\n";
    }
    else{
        fout<<0<<"\n";
    }

   }
    
    return 0;
}