/*
n - nr stari
m - numar tranzitii
nod_initial
q1 q2 c
nr_q - nr stari finale
q0 - stari finale
cuvinte

a) sa verifice daca un cuvant se accepta sau nu
b) analog daca e nedeterminist
c) cele mai scurte 100 de cuvinte care functioneaza
*/
#include <bits/stdc++.h>

using namespace std;

ifstream f("nfa.in");
ofstream g("nfa.out");

class Automat
{
private:
    unordered_map <char, vector<int>> node[1000];
    int n, m;//numar de stari + numar de tranzitii
    //node[q1][ce caracter am][al catelea]
    unordered_map<int, bool> final_nodes;
    int t;
    int init_node;
    vector <string> cuvinte;
public:
    Automat()
    {
        vector <int> aux;
        f >> this->n >> this->m;
        f >> t;
        f >> this->init_node;
        for (int i = 1; i <= t; i++)
        {
            int aux;
            f >> aux;
            final_nodes[aux] = 1;
        }
        for (int i = 1; i<= m; i++)
        {
            int q1, q2;
            char c;
            f >> q1 >> q2 >> c;
            this->node[q1][c].push_back(q2);
        }
        


    }
    bool verifica (string str);
    bool genereaza ();
    void afiseaza();
};


void Automat::afiseaza()
{
    for (int i = 0 ; i < 100; i++)
    {
        g<<this->cuvinte[i]<<"\n";
    }
}

// ---- generez primele 100 de cuvinte sau returnez imposibil;

bool Automat::genereaza()
{
    int afisate = 0;
    bool flag = 0;
    queue <string> q_string;
    queue <int> q_nod;
    unordered_map<string, bool> am_fost;
    int nod;
    string s = "";
    string s_aux;
    q_string.push(s);
    q_nod.push(this->init_node);
    while (afisate < 100)
    {
        if (q_nod.size() == 0 or q_nod.size() > 3000000)
            return 0;
        nod = q_nod.front();
        s = q_string.front();
        q_nod.pop();
        q_string.pop();
        if (final_nodes[nod] == 1)
        {
            afisate++;
            cuvinte.push_back(s);
        }
       
        s_aux = s + to_string(nod);
        if (am_fost[s_aux] == 0)
        {
            am_fost[s_aux] = 1;
            for (auto &it : node[nod])
            {
                s_aux = s  + it.first;
                for (auto &it2 : it.second)
                {
                    q_nod.push(it2);
                    q_string.push(s_aux);
                }
            }
        }
    }
    if (afisate < 100)
    return 0;
    return 1;

}


bool Automat::verifica (string str)
{
    int Size = str.size();
    int poz;
    int nod;
    queue <int> q_l, q_n;
    q_l.push(0);
    q_n.push(this->init_node);
    string s;
    unordered_map <string, bool> am_fost;
    while (!q_n.empty())
    {
        nod = q_n.front();
        poz = q_l.front();
        s = to_string(nod) + "$" + to_string(poz);
        q_n.pop();
        q_l.pop();
        if (poz == Size and final_nodes[nod] == 1)
        {
            return 1;
        }
        if (am_fost[s] == 0 and poz < Size)
        {
        am_fost[s] = 1;
        for (int i = 0; i < this->node[nod][str[poz]].size(); i ++)
        {
            q_n.push(this->node[nod][str[poz]][i]);
            q_l.push(poz + 1);
        }
        }
     }
    return 0;
}

int main()
{   

    Automat aut;
    string str = "";
    int n;
    f >> n;
    for (int i = 0; i < n; i++)
    {
        f >> str;
        g << aut.verifica(str) << "\n";
    }

    return 0;
}