#include <fstream>
#include <vector>
#include <utility>
#include <string>
#include <queue>

using namespace std;

const int NMAX = 1005;

struct Automat
{
    int statesNo, edgesNo, initialState, finalStatesNo;
    bool finalStates[NMAX];
    vector<pair<int, char>> g[NMAX];
} myAutomata;

vector<string> tests;

void citire()
{
    ifstream fin("nfa.in");

    fin >> myAutomata.statesNo >> myAutomata.edgesNo >> myAutomata.finalStatesNo;
    fin >> myAutomata.initialState;
    for (int i = 0; i < myAutomata.finalStatesNo; i++)
    {
        int x;
        fin >> x;
        myAutomata.finalStates[x] = true;
    }

    for (int i = 0; i < myAutomata.edgesNo; i++)
    {
        int x, y;
        char ch;
        fin >> x >> y >> ch;
        myAutomata.g[x].push_back(make_pair(y, ch));
    }

    int testsNo;
    fin >> testsNo;
    for (int i = 0; i < testsNo; i++)
    {
        string str;
        fin >> str;
        tests.push_back(str);
    }

    fin.close();
}

bool verif(string str)
{
    queue<int> q, temp;
    q.push(myAutomata.initialState);
    for (int i = 0; i < str.size(); i++)
    {
        while (!q.empty())
        {
            int elem = q.front();
            for (int k = 0; k < myAutomata.g[elem].size(); k++)
            {
                if (myAutomata.g[elem][k].second == str[i])
                {
                    temp.push(myAutomata.g[elem][k].first);
                }
            }
            q.pop();
        }

        while (!temp.empty())
        {
            q.push(temp.front());
            temp.pop();
        }
    }

    while (!q.empty())
    {
        if (myAutomata.finalStates[q.front()])
        {
            return true;
        }
        q.pop();
    }
    return false;
}

int main()
{
    citire();

    ofstream fout("nfa.out");

    for (auto test : tests)
    {
        if (verif(test))
        {
            fout << "1" << '\n';
        }
        else
        {
            fout << "0" << '\n';
        }
    }

    fout.close();

    return 0;
}