// Antonio-Alexandru Ganea // Grupa 135 // Tema LFA - Cazurile a) b) // Automat determinist/nedeterminist

#include <stdio.h>
#include <vector>
#include <map>
#include <string.h>

FILE * fin;

struct Node{
    std::map< char, std::vector<int> > m;
    bool finalState;
    Node(){
        finalState = false;
    }
};

bool vectorContains( std::vector<int> myvec, int number ){
    for (std::vector<int>::iterator it = myvec.begin() ; it != myvec.end(); ++it){
        if ( *it == number ){
            return true;
        }
    }
    return false;
}

void printVector( std::vector<int> myvec ){
    for (std::vector<int>::iterator it = myvec.begin() ; it != myvec.end(); ++it)
        printf("%d ",*it);
    puts("");
}

bool checkIfStatesContainFinishingState( Node nodes[], std::vector<int> myvec ){
    for (std::vector<int>::iterator it = myvec.begin() ; it != myvec.end(); ++it) {
        if ( nodes[*it].finalState ) {
            return true;
        }
    }
    return false;
}

FILE * fout;

int main(){
    fin = fopen( "nfa.in", "r" );
    fout = fopen("nfa.out","w");

    int states, transitions,finalStates;
    fscanf(fin,"%d%d%d",&states,&transitions,&finalStates);

    int initialState;

    Node nodes[states+1];

    fscanf(fin,"%d",&initialState);

    for ( int i = 0; i < finalStates; i++ ){
        int temp;
        fscanf(fin,"%d",&temp);
        nodes[temp].finalState = true;
    }



    for ( int i = 0; i < transitions; i++ ){
        int a,b;
        char temp[100];
        fscanf(fin,"%d%d%s",&a,&b,&temp);
        char c = temp[0];

        // din a in b prin c
        nodes[a].m[c].push_back(b);
    }





    int words;
    fscanf(fin,"%d",&words);

    for ( int currentWord = 0; currentWord < words; currentWord++ ){

        char word[1000];
        fscanf(fin,"%s",&word);

        std::vector<int> currentStates;
        currentStates.push_back(initialState);

        std::vector<int> nextStates;

        // puts("Current states:");
        // printVector(currentStates);

        for ( int i = 0; i < strlen(word); i++ ){
            nextStates.clear();
            // iterate through current states
            for (std::vector<int>::iterator it = currentStates.begin() ; it != currentStates.end(); ++it){
                // iterate through current state next states on current character
                for( std::vector<int>::iterator it2 = nodes[*it].m[word[i]].begin(); it2 != nodes[*it].m[word[i]].end(); ++it2 ){
                    if ( ! vectorContains(nextStates, *it2) ){
                        nextStates.push_back(*it2);
                    }
                }
            }
            currentStates.clear();
            currentStates.assign(nextStates.begin(), nextStates.end());

            // puts("Current states:");
            // printVector(currentStates);
        }

        if ( checkIfStatesContainFinishingState( nodes, currentStates ) ) {
            fprintf(fout,"1\n", word);
        } else {
            fprintf(fout,"0\n", word);
        }
    }
    fclose(fout);
    return 0;
}