#include <bits/stdc++.h>
using namespace std;

class Automat {
private:
    int nrStates;
    const int SZ = 30;
    vector <vector <vector <int> > > transitions;
    vector <vector <vector <int> > > transitionsInv;
    vector <bool> finalStates;
    vector <bool> isUseless;

    struct nodeStates{
        int node, len;

        bool operator<(const nodeStates& other)const{
            if (len == other.len) return node < other.node;
            else return len < other.len;
        }
    };


public:
    int initialState;
    map <nodeStates, bool> badStates;

    friend istream& operator>> (istream& in, Automat& ob){
        int m, t;
        in >> ob.nrStates >> m >> t;
        ob.finalStates.resize(ob.nrStates, 0);
        ob.isUseless.resize(ob.nrStates, 0);
        in >> ob.initialState;
        ob.initialState--;
        for (int i=0; i<t; i++){
            int x;
            in >> x;
            x--;
            ob.finalStates[x] = 1;
        }
        ob.transitions.resize(ob.nrStates, vector <vector <int> > (ob.SZ));
        ob.transitionsInv.resize(ob.nrStates, vector <vector <int> > (ob.SZ));
        for (int i=0; i<m; i++){
            int x, y; char c;
            in >> x >> y >> c;
            x--; y--;
            ob.transitions[x][c - 'a'].push_back(y);
            ob.transitionsInv[y][c - 'a'].push_back(x);
        }
        ob.removeUselessStates();
        return in;
    }
    void removeUselessStates(){
        queue <int> Q;
        for (int i=0; i < nrStates; i++){
            if (finalStates[i]) Q.push(i), isUseless[i] = 1;
        }
        while (!Q.empty()){
            int nod = Q.front();
            Q.pop();
            for (char c='a'; c<='z'; c++){
                for (int &it: transitionsInv[nod][c - 'a']){
                    if (!isUseless[it]) Q.push(it), isUseless[it] = 1;
                }
            }
        }
        for (int i=0; i < nrStates; i++) isUseless[i] = !isUseless[i];
    }
    bool isAccepted(string& word, int nod, int idx = 0){
        if (idx == (int) word.length()) return finalStates[nod];
        if (!transitions[nod][word[idx] - 'a'].size()) return 0;
        for (int &it: transitions[nod][word[idx] - 'a']){
            if (isUseless[it]) continue;
            if (badStates[{it, idx + 2}]) continue;
            if (isAccepted(word, it, idx + 1)) return 1;
        }
        badStates[{nod, idx + 1}] = 1;
        return 0;
    }
};

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

int main(){
    Automat automat;
    in >> automat;

    int nrWords;
    in >> nrWords;
    string word;
    getline(in, word);
    while (nrWords--){
        getline(in, word);
        out << automat.isAccepted(word, automat.initialState) << '\n';
        //if (automat.isAccepted(word, automat.initialState))
        //    cout << word << " apartine automatului\n";
        //else cout << word << " nu apartine automatului\n";
        automat.badStates.clear();
    }
    return 0;
}