#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <climits>

using namespace std;

const int NMAX = 305;

struct Automat
{
    int statesNo, edgesNo, initialState, finalStatesNo;
    bool finalStates[NMAX];
    bool g[NMAX][NMAX][30];
    vector<int> nxt[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);
        if (!myAutomata.g[x][y][ch - 'a'])
        {
            myAutomata.nxt[x][ch - 'a'].push_back(y);
        }
        myAutomata.g[x][y][ch - 'a'] = true;
    }
}

char str[155];
queue<int> q;

bool verif()
{
    fgets(str, 155, stdin);
    int n = strlen(str) - 1;
    q.push(myAutomata.initialState);
    q.push(INT_MAX);
    for (int i = 0; i < n; i++)
    {
        while (q.front() != INT_MAX)
        {
            int x = q.front();

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

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

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

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