#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[1000];
    vector<int> muchie[1000][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);
    }
}

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

    }
    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;
}