#include <bits/stdc++.h>
//#include "Automat.cpp"
#include <unordered_set>
using namespace std;
ifstream fin("nfa.in");
ofstream fout("nfa.out");

class Automat{
private:
    int n, m;
    int nod_init;
    bool is_final[310];
    int vec[310];
    vector<int> muchie[310][30];
    int n_final_nodes;  
public:
    friend ifstream& operator >> (ifstream& , Automat &);
    bool checkWord(string &);
};

ifstream& operator >> (ifstream& fin, Automat &obj)
{
    int aux, nods, nodf;
    char c;
    fin >> obj.n >> obj.m >> obj.n_final_nodes;
    fin >> obj.nod_init;
    for (int i = 0 ; i <= obj.n; i++)
    {
        obj.is_final[i] = false;
    }
    for (int i = 1; i<= obj.n_final_nodes; i++)
    {
        fin >> aux;
        obj.is_final[aux] = true;
    }
    for (int i = 1; i<= obj.m; i++)
    {
        fin >> nods >> nodf >> c;
        obj.muchie[nods][c - 'a'].push_back(nodf);
    }
    return fin;
}

bool Automat::checkWord(string &s)
{
    unordered_set  <int> nodes;
    nodes.insert(nod_init);
    int i,j,k;
    for(i = 0; i < s.size(); i++)
    {
        vec[0] = 0;
        for (auto nod : nodes)
        {
            vec[0] ++;
            vec[vec[0]] = nod;
        }
        nodes.clear();

        for (k = 1; k <= vec[0]; k++) 
        {
            for (j = 0; j < muchie[vec[k]][s[i] - 'a'].size(); j++)
            {
                nodes.insert( muchie[vec[k]][s[i] - 'a'][j]);
            }
        }

    }
    for (auto &nod : nodes)
        if (is_final[nod] == true)
            return 1;
    return 0;
}


int main()
{

    Automat aut;
    fin >> aut;
    string s;
    int n;
    fin >> n;
    for (int i = 1 ; i <= n; i++)
    {
        fin >> s;
        fout << aut.checkWord(s) <<"\n";

    }

    
    return 0;
}