#include <cstdio>
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <climits>

using namespace std;

const int NMAX = 305;

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

vector<string> tests;

void citire()
{
    scanf("%d%d%d%d", &myAutomata.statesNo, &myAutomata.edgesNo, &myAutomata.finalStatesNo, &myAutomata.initialState);

    for (int i = 0; i < myAutomata.finalStatesNo; i++)
    {
        int x;
        scanf("%d", &x);
        myAutomata.finalStates[x] = true;
    }

    for (int i = 0; i < myAutomata.edgesNo; i++)
    {
        int x, y;
        char ch;
        scanf("%d%d ", &x, &y);
        ch = getc(stdin);
        myAutomata.g[x][ch - 'a'].push_back(y);
    }
}

bool verif()
{
    string str;
    cin >> str;
    queue<int> q;
    q.push(myAutomata.initialState);
    q.push(INT_MAX);
    for (int i = 0; i < str.size(); i++)
    {
        while (q.front() != INT_MAX)
        {
            int x = q.front();

            for (auto y : myAutomata.g[x][str[i] - 'a'])
            {
                q.push(y);
            }

            q.pop();
        }
        q.pop();
        q.push(INT_MAX);
    }

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

int main()
{
    freopen("nfa.in", "r", stdin);
    freopen("nfa.out", "w", stdout);

    citire();

    int testsNo;
    scanf("%d\n", &testsNo);
    for (int i = 0; i < testsNo; i++)
    {
        if (verif())
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    return 0;
}