#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>

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

int x, y, n, m, S, nrF, nrCuv;
char l;
std::set<int> final_states;
std::map<int, std::map<char, std::vector<int>>> states;
std::map<int,std::vector<bool>> state_visited_at_index;
std::string str;
bool succesful;

void NFA(std::string str, int state, int index) {
	if (!succesful) {
		if (index < str.length()) {
			for (int possible_state : states[state][str[index]]) {
				if (state_visited_at_index[possible_state][index] == 0) {
					state_visited_at_index[possible_state][index] = 1;
					NFA(str, possible_state, index + 1);
				}
			}
		}
		else if (index == str.length()) {
			if (final_states.find(state) != final_states.end()) { succesful = true; }
		}
	}
}

int main() {

	in >> n >> m >> nrF;
	in >> S;
	for (int i = 0; i < nrF; i++) {
		in >> x;
		final_states.insert(x);
	}
	for (int i = 0; i < m; i++) {
		in >> x >> y;
		in >> l;
		in.get();
		states[x][l].push_back(y);
	}

	in >> nrCuv;
	for (int i = 0; i < nrCuv; i++) {
		in >> str;
		for(int i = 1; i <= n; i++) {
			state_visited_at_index[i] = std::vector<bool>(str.length(), 0);;
		}
		succesful = false;
		NFA(str,S, 0);
		if (succesful) { out << 1 << std::endl; }
		else { out << 0 << std::endl; }
	}
	return 0;
}