#include <iostream>
#include <string>
#include <fstream>
#include <unordered_map>

const std::string DICTIONARY_PATH = "input.txt";
const std::string REQUESTS_PATH = "req.txt";
const std::string OUTPUT_PATH = "output.txt";

class StringsStore
{
public:
	void AddString(const std::string& str);
	bool FindString(const std::string& str) const;

private:
	struct Node
	{
		Node() : finish(false) {}
		bool finish;
		std::unordered_map<char, Node> children;
	} root_;
};

void StringsStore::AddString(const std::string& str)
{
	Node * current = &root_;

	for (char s : str)
	{
		if (current->children.find(s) == current->children.end())
			current->children.insert(std::make_pair(s, Node()));
		current = &current->children[s];
	}

	current->finish = true;
}

bool StringsStore::FindString(const std::string& str) const
{
	const Node* current = &root_;
	for (char s : str)
	{
		const auto& child = current->children.find(s);
		if (child == current->children.end())
			return false;

		current = &child->second;
	}

	return current->finish;
}

namespace StringsStoreHelper
{
	StringsStore ReadFromFile(const std::string& path)
	{
		StringsStore store;
		std::ifstream infile(path);
		std::string line;
		while (std::getline(infile, line))
			store.AddString(line);

		return store;
	}
}


int main()
{
	StringsStore store = StringsStoreHelper::ReadFromFile(DICTIONARY_PATH);

	std::ifstream reqfile(REQUESTS_PATH);
	std::ofstream outfile(OUTPUT_PATH);

	std::string line;
	while (std::getline(reqfile, line))
		outfile << store.FindString(line) << "\n";
	return 0;
}