//#ifdef ONLINE_JUDGE
//#define NDEBUG
//#endif
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <limits>
#include <map>
#include <queue>
#include <algorithm>
#ifndef NDEBUG
#include <string>
#endif
#define MAX_S_LENGTH 100000
#define MAX_T_LENGTH 1000
#define MAX_K 10
#define MAX_Q 1000
#define ALPHA ('Z' - 'A' + 1 + 'z' - 'a' + 1 + 1)
#define ENCODE(c) (isupper((c)) ? c - 'A' + 1 : c ? 'Z' - 'A' + 1 + c - 'a' + 1 : 0)
class Ukkonen
{
class Edge
{
public:
static const int INFTY = std::numeric_limits<int>::max();
protected:
int begin; //inclusive
int end; //exclusive
const Ukkonen *ukkonen;
Edge(int begin, int end, const Ukkonen *ukkonen) :
begin(begin),
end(end),
ukkonen(ukkonen)
{}
public:
int &getBegin() {return begin;}
int getBegin() const {return begin;}
int getEnd() const {return INFTY == end ? ukkonen->length : end; }
int getLength() const {return getEnd() - getBegin(); }
};
struct Node : public Edge
{
Node *parent;
Node *link;
Node *children[ALPHA];
Node(int begin, int end, const Ukkonen *ukkonen):
Edge(begin, end, ukkonen),
parent(NULL),
link(NULL)
{memset(children, NULL, sizeof(children));};
~Node()
{
for (const auto &child : children)
{
delete child;
}
}
};
struct State
{
Node *node;
int position; // on edge which enters node
State(Node *node, int position) : node(node), position(position) {}
};
int go(State &state, const char needle[], int begin, int end)
{
while (begin < end)
{
assert(state.position <= state.node->getLength());
if (state.node->getLength() == state.position)
{
if (state.node->children[needle[begin]])
{
state.node = state.node->children[needle[begin]];
state.position = 0;
}
else
{
break;
}
}
else if (needle[begin] == buffer[state.node->getBegin() + state.position])
{
++begin;
++state.position;
}
else
{
break;
}
}
return end - begin;
}
Node *split(const State &state)
{
Node *separator;
assert(0 <= state.position && state.position <= state.node->getLength());
if (state.node->getLength() == state.position)
{
separator = state.node;
}
else if (0 == state.position)
{
separator = state.node->parent;
}
else
{
separator = new Node(state.node->getBegin(), state.node->getBegin() + state.position, this);
separator->parent = state.node->parent;
separator->children[buffer[state.node->getBegin() + state.position]] = state.node;
assert(0 == state.node->getLength() || state.node->parent->children[buffer[state.node->getBegin()]] == state.node);
state.node->parent->children[buffer[state.node->getBegin()]] = separator;
state.node->getBegin() = state.node->getBegin() + state.position;
state.node->parent = separator;
}
setLink(nodeWithoutLink, separator);
nodeWithoutLink = separator;
return separator;
}
void extend(int position)
{
assert(position == length);
++length;
nodeWithoutLink = &dummyNode;
while(true)
{
State copy = state;
int left = go(state, buffer, position, position + 1);
if (0 == left)
{
assert(0 != memcmp(©, &state, sizeof(State)));
if (copy.position == copy.node->getLength())
{
setLink(nodeWithoutLink, copy.node);
}
nodeWithoutLink = &dummyNode;
break;
}
assert(left == 1);
assert(0 == memcmp(&state, ©, sizeof(State)));
Node *separator = split(state);
Node *leaf = new Node(position, Edge::INFTY, this);
// assert(root == separator || 0 < separator->children.size());
assert(0 == separator->children[buffer[position]]);
separator->children[buffer[position]] = leaf;
leaf->parent = separator;
state.node = separator->parent->link;
state.position = separator->parent->link->getLength();
int zero = go(state, buffer, separator->getBegin() + (root == separator->parent), separator->getEnd());
assert(0 >= zero);
if (root == leaf->parent)
{
break;
}
}
setLink(nodeWithoutLink, root);
}
void setLink(Node *node, Node *suffixNode)
{
assert(&dummyNode == node || NULL == node->link || suffixNode == node->link);
node->link = suffixNode;
assert(root == nodeWithoutLink || &dummyNode == nodeWithoutLink || getString(node).substr(1) == getString(suffixNode));
}
#ifndef NDEBUG
std::string getString(Node *vertex)
{
std::string result = "";
while (root != vertex)
{
for (int i = vertex->getEnd() - 1; i >= vertex->getBegin(); --i)
{
result += buffer[i];
}
vertex = vertex->parent;
}
std::reverse(result.begin(), result.end());
return result;
}
#endif
public:
Ukkonen(const char input[]):
buffer(new char[strlen(input) + 1]),
root(new Node(0, 0, this)),
state(root, 0),
nodeWithoutLink(NULL),
dummyNode(-1, -1, this),
length(0)
{
int i;
for (i = 0; input[i]; ++i)
{
buffer[i] = ENCODE(input[i]);
}
buffer[i] = ENCODE('\0');
int position;
root->parent = root;
root->link = root;
nodeWithoutLink = &dummyNode;
for (position = 0; buffer[position]; ++position)
{
extend(position);
}
extend(position);
}
~Ukkonen()
{
delete [] buffer;
delete root;
}
bool isSubstring(const char substring[])
{
static char encodedSubstring[MAX_T_LENGTH + 1];
int length = (int)strlen(substring);
State state(root, 0);
for (int i = 0; i <= length; ++i)
{
encodedSubstring[i] = ENCODE(substring[i]);
}
int left = go(state, encodedSubstring, 0, length);
assert(0 <= left);
return 0 == left;
}
private:
char *buffer;
Node *root;
Node *nodeWithoutLink;
State state;
Node dummyNode;
int length;
};
template <class Callback>
void iterateOverStrings(int lengthBegin, int lengthEnd, Callback callback)
{
assert(lengthBegin <= lengthEnd);
const int alpha = 'z' - 'a' + 1;
const unsigned long long beginMask = 0;
unsigned long long endMask = 1;
for (int length = 0; length < lengthEnd; ++length)
{
if (lengthBegin <= length)
{
char buffer[length + 1];
for (unsigned long long mask = beginMask; mask < endMask; ++mask)
{
unsigned long long maskCopy = mask;
for (int index = 0; index < length; ++index)
{
buffer[index] = maskCopy % alpha + 'a';
maskCopy /= alpha;
}
assert(0 == maskCopy);
buffer[length] = '\0';
callback(buffer);
}
}
endMask *= alpha;
}
}
void uva_10679()
{
int k;
scanf("%d", &k);
for (int testcase = 0; testcase < k; ++testcase)
{
static char s[MAX_S_LENGTH + 1];
int q;
scanf(" %s%d", s, &q);
Ukkonen ukkonen(s);
for (int query = 0; query < q; ++query)
{
static char t[MAX_T_LENGTH + 1];
scanf(" %s", t);
if (ukkonen.isSubstring(t))
{
printf("y\n");
}
else
{
printf("n\n");
}
}
}
}
void unitTest()
{
assert(0 == ENCODE('\0'));
assert(1 == ENCODE('A'));
assert(26 == ENCODE('Z'));
assert(27 == ENCODE('a'));
assert(52 == ENCODE('z'));
srand(42);
{
Ukkonen ukkonen("bbaabbbab");
assert(ukkonen.isSubstring("bab"));
}
{
Ukkonen ukkonen("abbaabbbabaaaabbabbaabbaaaaabaaabbaaaabbbbbabbbbaabbbabaaaaaaaaaaaaaabbaabababaabbbbbbbbbbbbbbbbaba");
assert(ukkonen.isSubstring("bab"));
}
{
Ukkonen ukkonen("ababc");
assert(ukkonen.isSubstring("bc"));
}
{
Ukkonen ukkonen("mfkfkhgv");
assert(ukkonen.isSubstring("kh"));
}
{
Ukkonen ukkonen("bba");
assert(ukkonen.isSubstring("ba"));
}
{
Ukkonen ukkonen("a");
assert(ukkonen.isSubstring(""));
assert(ukkonen.isSubstring("a"));
assert(!ukkonen.isSubstring("b"));
assert(!ukkonen.isSubstring("aa"));
}
{
Ukkonen ukkonen("aa");
assert(ukkonen.isSubstring(""));
assert(ukkonen.isSubstring("a"));
assert(ukkonen.isSubstring("aa"));
assert(!ukkonen.isSubstring("b"));
}
{
Ukkonen ukkonen("ab");
assert(ukkonen.isSubstring(""));
assert(ukkonen.isSubstring("a"));
assert(ukkonen.isSubstring("b"));
assert(!ukkonen.isSubstring("aa"));
assert(!ukkonen.isSubstring("ba"));
}
{
Ukkonen ukkonen("");
assert(ukkonen.isSubstring(""));
assert(!ukkonen.isSubstring("a"));
}
struct CheckCallback
{
Ukkonen &ukkonen;
const char *string;
void operator()(const char substring[]) const
{
bool isSubstringAnswer = NULL != strstr(string, substring);
bool isSubstringOutput = ukkonen.isSubstring(substring);
fprintf(stderr, "Is \"%s\" substring of \"%s\"?\n\tUkkonen: %d\n\tCorrect answer: %d\n", substring, string, isSubstringOutput, isSubstringAnswer);
assert(isSubstringAnswer == isSubstringOutput);
}
CheckCallback(Ukkonen &ukkonen, const char string[]) : ukkonen(ukkonen), string(string){}
};
{
while (true)
{
enum
{
STRING,
SUBSTRING,
NUMBER
};
int length[NUMBER];
char *string[NUMBER];
for (int i = 0; i < NUMBER; ++i)
{
length[i] = rand() % 10;
string[i] = new char[length[i] + 1];
for (int j = 0; j < length[i]; ++j)
{
string[i][j] = (char)(rand() % ('z' - 'a' + 1) + 'a');
}
string[i][length[i]] = '\0';
}
Ukkonen ukkonen(string[STRING]);
CheckCallback check(ukkonen, string[STRING]);
check(string[SUBSTRING]);
for (int i = 0; i < NUMBER; ++i)
{
delete [] string[i];
}
}
}
{
struct TestCallback
{
void operator()(const char buffer[]) const
{
Ukkonen ukkonen(buffer);
iterateOverStrings(0, (int)strlen(buffer) + 1, CheckCallback(ukkonen, buffer));
}
};
iterateOverStrings(0, 3, TestCallback());
}
assert(true);
}
void profileTestCreate()
{
freopen("input.txt", "w", stdout);
int k = MAX_K;
printf("%d\n", k);
for (int testcase = 0; testcase < k; ++testcase)
{
static char s[MAX_S_LENGTH + 1];
for (int i = 0; i < MAX_S_LENGTH; ++i)
{
s[i] = (rand() & 1 ? 'a' : 'A') + rand() % ('Z' - 'A' + 1);
}
s[MAX_S_LENGTH] = '\0';
int q = MAX_Q;
printf("%s\n%d\n", s, q);
for (int query = 0; query < q; ++query)
{
static char t[MAX_T_LENGTH + 1];
for (int i = 0; i < MAX_T_LENGTH; ++i)
{
t[i] = (rand() & 1 ? 'a' : 'A') + rand() % ('Z' - 'A' + 1);
}
t[MAX_T_LENGTH] = '\0';
printf("%s\n", t);
}
}
fflush(stdout);
}
void profileTestRun()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
uva_10679();
}
int main()
{
//unitTest();
//profileTestCreate();
//profileTestRun();
uva_10679();
return 0;
}