//
// 10679-i-love-strings.cpp
// 10679-I-Love-Strings
//
// Created by Volodymyr Polosukhin on 10/10/2017.
// Copyright © 2017 Volodymyr Polosukhin. All rights reserved.
//
#define NDEBUG
#include <cstdio>
#include <cassert>
#include <cctype>
#include <cstring>
#include <limits>
#define INFTY (std::numeric_limits<int>::max())
#define CHARACTERS_NUMBER (('z' - 'a' + 1) + ('Z' - 'A' + 1) + 1)
#define ILLEGAL_INDEX (0)
#define MAX_S_LENGTH (100000)
#define MAX_T_LENGTH (1000)
int length;
int nodesSize;
struct Node
{
int begin;
int end;
int parent;
int link;
int characterToNode[CHARACTERS_NUMBER];
int getBegin() const { return begin; }
int getEnd() const { return INFTY == end ? length : end; }
int getLength() const { return getEnd() - getBegin(); }
};
char buffer[MAX_S_LENGTH + 1];
Node nodes[MAX_S_LENGTH + 2];
int dummy;
int root;
int currentPosition;
int currentNode;
inline int go(int ¤tNode, int ¤tPosition, const char needle[], int begin, int end)
{
while (begin < end)
{
assert(currentNode < nodesSize);
assert(currentPosition <= nodes[currentNode].getLength());
if (nodes[currentNode].getLength() == currentPosition)
{
if (ILLEGAL_INDEX == nodes[currentNode].characterToNode[needle[begin]])
{
break;
}
currentNode = nodes[currentNode].characterToNode[needle[begin]];
currentPosition = 0;
}
else if (needle[begin] == buffer[nodes[currentNode].begin + currentPosition])
{
++begin;
++currentPosition;
}
else
{
break;
}
}
return begin < end ? end - begin : 0;
}
inline void extend(char character)
{
buffer[length++] = character;
int nodeWithoutLink = dummy;
while (true)
{
int previousPosition = currentPosition;
int previousNode = currentNode;
int left = go(currentNode, currentPosition, buffer, length - 1, length);
if (0 == left)
{
if (previousPosition == nodes[previousNode].getLength())
{
nodes[nodeWithoutLink].link = previousNode;
nodeWithoutLink = dummy;
}
break;
}
assert(1 == left);
assert(previousNode == currentNode);
assert(previousPosition == currentPosition);
assert(0 <= currentPosition && currentPosition <= nodes[currentNode].getLength());
int separator;
if (nodes[currentNode].getLength() == currentPosition)
{
separator = currentNode;
}
else if (0 == currentPosition)
{
separator = nodes[currentNode].parent;
}
else
{
separator = nodesSize++;
nodes[separator].begin = nodes[currentNode].getBegin();
nodes[separator].end = nodes[currentNode].getBegin() + currentPosition;
nodes[separator].parent = nodes[currentNode].parent;
nodes[separator].characterToNode[buffer[nodes[currentNode].getBegin() + currentPosition]] = currentNode;
assert(0 == nodes[currentNode].getLength() || nodes[nodes[currentNode].parent].characterToNode[buffer[nodes[currentNode].getBegin()]] == currentNode);
nodes[nodes[currentNode].parent].characterToNode[buffer[nodes[currentNode].getBegin()]] = separator;
nodes[currentNode].begin += currentPosition;
nodes[currentNode].parent = separator;
assert(nodes[currentNode].begin <= nodes[currentNode].end);
}
nodes[nodeWithoutLink].link = separator;
nodeWithoutLink = separator;
int leaf = nodesSize++;
assert(ILLEGAL_INDEX == nodes[separator].characterToNode[character]);
nodes[separator].characterToNode[character] = leaf;
nodes[leaf].begin = length - 1;
nodes[leaf].end = INFTY;
nodes[leaf].parent = separator;
currentNode = nodes[nodes[separator].parent].link;
currentPosition = nodes[currentNode].getLength();
assert(ILLEGAL_INDEX != currentNode);
int zero = go(currentNode, currentPosition, buffer, nodes[separator].getBegin() + (root == nodes[separator].parent), nodes[separator].getEnd());
assert(0 >= zero);
if (root == separator)
{
break;
}
nodes[nodeWithoutLink].link = root;
}
}
inline void init()
{
length = 0;
nodesSize = 2;
dummy = ILLEGAL_INDEX;
root = 1;
currentPosition = 0;
currentNode = root;
memset(nodes, 0, sizeof(nodes));
nodes[root].begin = nodes[root].end = 0;
nodes[root].parent = nodes[root].link = root;
}
inline void ukkonen(const char buffer[])
{
init();
for (const char *pointer = buffer; *pointer; ++pointer)
{
extend(*pointer);
}
extend('\0');
}
inline bool isSubstring(int length, const char needle[])
{
int currentNode = root;
int currentPosition = 0;
int left = go(currentNode, currentPosition, needle, 0, length);
assert(0 <= left);
return 0 == left;
}
void encodeString(char string[])
{
for (char *pointer = string; *pointer; ++pointer)
{
if (isupper(*pointer))
{
*pointer = (*pointer - 'A') + 1;
}
else
{
assert(islower(*pointer));
*pointer = (*pointer - 'a') + ('Z' - 'A' + 1) + 1;
}
}
}
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);
encodeString(s);
ukkonen(s);
for (int query = 0; query < q; ++query)
{
static char t[MAX_T_LENGTH + 1];
scanf(" %s", t);
encodeString(t);
if (isSubstring(strlen(t), t))
{
printf("y\n");
}
else
{
printf("n\n");
}
}
}
}
void unit_test()
{
{
char s[] = "abcdefghABCDEFGH";
encodeString(s);
ukkonen(s);
{
char t[] = "abc";
encodeString(t);
assert(true == isSubstring(3, t));
}
{
char t[] = "abAB";
encodeString(t);
assert(false == isSubstring(4, t));
}
}
{
char s[] = "xyz";
encodeString(s);
ukkonen(s);
char t[] = "xyz";
encodeString(t);
assert(true == isSubstring(3, t));
}
}
int main()
{
//unit_test();
uva_10679();
return 0;
}