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

class Automat {
private:
    int nrStates;
    vector <map <char, set<int> > > transitions;
    vector <map <char, set<int> > > transitionsInv;
    vector <bool> isFinal;
    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.isFinal.resize(ob.nrStates);
        ob.isUseless.resize(ob.nrStates);
        in >> ob.initialState;
        ob.initialState--;
        for (int i=0, x; i<t; i++){
            in >> x;
            x--;
            ob.isFinal[x] = 1;
        }
        ob.transitions.resize(ob.nrStates);
        ob.transitionsInv.resize(ob.nrStates);
        for (int i=0; i<m; i++){
            int x, y; char c;
            in >> x >> y >> c;
            x--; y--;
            ob.transitions[x][c].insert(y);
            ob.transitionsInv[y][c].insert(x);
        }
        ob.removeUselessStates();
        return in;
    }
    void removeUselessStates(){
        queue <int> Q;
        for (int i=0; i < nrStates; i++){
            if (isFinal[i]) Q.push(i), isUseless[i] = 1;
        }
        while (!Q.empty()){
            int nod = Q.front();
            Q.pop();
            for (auto &edge: transitionsInv[nod]){
                for (const int &it: edge.second){
                    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 isFinal[nod];
        if (!transitions[nod].count(word[idx])) return 0;
        for (const int &it: transitions[nod][word[idx]]){
            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';
        automat.badStates.clear();
    }
    return 0;
}