#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define PB push_back
#define MAX 100010
struct node
{
char ch;
node *next[26], *fail, *pa;
vector<int> output;
node()
{
pa = fail = NULL;
FOR(i,0,25) next[i] = NULL;
}
};
node *Root;
int ID(char ch)
{
int ret = 0;
if(ch < 'a') ret = ch - 'A';
else ret = ch - 'a';
return ret;
}
void in(string str,int p)
{
node *s = Root;
int n = str.size();
FOR(i,0,n-1)
{
int x = ID( str[i] );
if(s->next[x] == NULL)
{
s->next[x] = new node();
s->next[x]->ch = str[i];
s->next[x]->pa = s;
}
s = s->next[x];
}
if(!s->output.size())
{
s->output.PB( p );
}
return;
}
queue<node*> que;
void outputLink(node *go,node *p)
{
for(auto oto : go->output) p->output.PB( oto );
}
void bfs(node *p)
{
que.push( p );
while(!que.empty())
{
p = que.front(); que.pop();
int C = ID( p->ch );
//cout << p->ch << endl;
if(p->pa == Root)
{
p->fail = Root;
}
else
{
node *s = p->pa->fail;
while(true)
{
///cout << s->lev << ' ' << s->ch << endl;
if(s->next[C] != NULL)
{
p->fail = s->next[C];
outputLink(s->next[C], p);
break;
}
else if(Root == s)
{
p->fail = Root;
break;
}
s = s->fail;
}
}
FOR(i,0,25)
{
if(p->next[i] != NULL)
{
que.push( p->next[i] );
}
}
}
}
string pattern[MAX], text;
vector<int> ocr[MAX];
void readText()
{
int p = 0, n = text.size(), x;
node *s = Root;
while(p < n)
{
int x = ID( text[p] );
if(s->next[x] != NULL)
{
s = s->next[x];
for(auto go : s->output)
{
ocr[p].PB( go );
}
p++;
}
else if(s == Root) p++;
else s = s->fail;
}
}
int main()
{
ios::sync_with_stdio(false);
///freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
Root = new node();
Root->fail = Root;
Root->pa = Root;
int n, q;
cin >> n;
cin >> text;
cin >> q;
FOR(i,0,q-1)
{
cin >> pattern[i];
in(pattern[i], i);
}
bfs( Root );
readText();
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZPUihpLGosaykgZm9yKGludCBpPWo7aTw9aztpKyspCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgTUFYIDEwMDAxMAoKc3RydWN0IG5vZGUKewogICAgY2hhciBjaDsKCiAgICBub2RlICpuZXh0WzI2XSwgKmZhaWwsICpwYTsKICAgIHZlY3RvcjxpbnQ+IG91dHB1dDsKCiAgICBub2RlKCkKICAgIHsKICAgICAgICBwYSA9IGZhaWwgPSBOVUxMOwogICAgICAgIEZPUihpLDAsMjUpIG5leHRbaV0gPSBOVUxMOwogICAgfQp9OwoKbm9kZSAqUm9vdDsKCmludCBJRChjaGFyIGNoKQp7CiAgICBpbnQgcmV0ID0gMDsKCiAgICBpZihjaCA8ICdhJykgcmV0ID0gY2ggLSAnQSc7CiAgICBlbHNlIHJldCA9IGNoIC0gJ2EnOwoKICAgIHJldHVybiByZXQ7Cn0KCnZvaWQgaW4oc3RyaW5nIHN0cixpbnQgcCkKewogICAgbm9kZSAqcyA9IFJvb3Q7CiAgICBpbnQgbiA9IHN0ci5zaXplKCk7CgogICAgRk9SKGksMCxuLTEpCiAgICB7CiAgICAgICAgaW50IHggPSBJRCggc3RyW2ldICk7CgogICAgICAgIGlmKHMtPm5leHRbeF0gPT0gTlVMTCkKICAgICAgICB7CiAgICAgICAgICAgIHMtPm5leHRbeF0gPSBuZXcgbm9kZSgpOwogICAgICAgICAgICBzLT5uZXh0W3hdLT5jaCA9IHN0cltpXTsKICAgICAgICAgICAgcy0+bmV4dFt4XS0+cGEgPSBzOwogICAgICAgIH0KICAgICAgICBzID0gcy0+bmV4dFt4XTsKICAgIH0KCiAgICBpZighcy0+b3V0cHV0LnNpemUoKSkKICAgIHsKICAgICAgICBzLT5vdXRwdXQuUEIoIHAgKTsKICAgIH0KICAgIHJldHVybjsKfQoKcXVldWU8bm9kZSo+IHF1ZTsKCnZvaWQgb3V0cHV0TGluayhub2RlICpnbyxub2RlICpwKQp7CiAgICBmb3IoYXV0byBvdG8gOiBnby0+b3V0cHV0KSBwLT5vdXRwdXQuUEIoIG90byApOwp9Cgp2b2lkIGJmcyhub2RlICpwKQp7CiAgICBxdWUucHVzaCggcCApOwoKICAgIHdoaWxlKCFxdWUuZW1wdHkoKSkKICAgIHsKICAgICAgICBwID0gcXVlLmZyb250KCk7IHF1ZS5wb3AoKTsKICAgICAgICBpbnQgQyA9IElEKCBwLT5jaCApOwogICAgICAgIC8vY291dCA8PCBwLT5jaCA8PCBlbmRsOwoKICAgICAgICBpZihwLT5wYSA9PSBSb290KQogICAgICAgIHsKICAgICAgICAgICAgcC0+ZmFpbCA9IFJvb3Q7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIG5vZGUgKnMgPSBwLT5wYS0+ZmFpbDsKCiAgICAgICAgICAgIHdoaWxlKHRydWUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vL2NvdXQgPDwgcy0+bGV2IDw8ICcgJyA8PCBzLT5jaCA8PCBlbmRsOwogICAgICAgICAgICAgICAgaWYocy0+bmV4dFtDXSAhPSBOVUxMKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHAtPmZhaWwgPSBzLT5uZXh0W0NdOwogICAgICAgICAgICAgICAgICAgIG91dHB1dExpbmsocy0+bmV4dFtDXSwgcCk7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIGlmKFJvb3QgPT0gcykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBwLT5mYWlsID0gUm9vdDsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBzID0gcy0+ZmFpbDsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgRk9SKGksMCwyNSkKICAgICAgICB7CiAgICAgICAgICAgIGlmKHAtPm5leHRbaV0gIT0gTlVMTCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcXVlLnB1c2goIHAtPm5leHRbaV0gKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCn0KCgpzdHJpbmcgcGF0dGVybltNQVhdLCB0ZXh0Owp2ZWN0b3I8aW50PiBvY3JbTUFYXTsKCnZvaWQgcmVhZFRleHQoKQp7CiAgICBpbnQgcCA9IDAsIG4gPSB0ZXh0LnNpemUoKSwgeDsKICAgIG5vZGUgKnMgPSBSb290OwoKICAgIHdoaWxlKHAgPCBuKQogICAgewogICAgICAgIGludCB4ID0gSUQoIHRleHRbcF0gKTsKICAgICAgICBpZihzLT5uZXh0W3hdICE9IE5VTEwpCiAgICAgICAgewogICAgICAgICAgICBzID0gcy0+bmV4dFt4XTsKICAgICAgICAgICAgZm9yKGF1dG8gZ28gOiBzLT5vdXRwdXQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG9jcltwXS5QQiggZ28gKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBwKys7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYocyA9PSBSb290KSBwKys7CiAgICAgICAgZWxzZSBzICA9IHMtPmZhaWw7CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgLy8vZnJlb3BlbigiaW4udHh0IiwgInIiLCBzdGRpbik7CiAgIC8vIGZyZW9wZW4oIm91dC50eHQiLCAidyIsIHN0ZG91dCk7CgogICAgUm9vdCA9IG5ldyBub2RlKCk7CiAgICBSb290LT5mYWlsID0gUm9vdDsKICAgIFJvb3QtPnBhID0gUm9vdDsKCiAgICBpbnQgbiwgcTsKCiAgICBjaW4gPj4gbjsKICAgIGNpbiA+PiB0ZXh0OwoKICAgIGNpbiA+PiBxOwogICAgRk9SKGksMCxxLTEpCiAgICB7CiAgICAgICAgY2luID4+IHBhdHRlcm5baV07CiAgICAgICAgaW4ocGF0dGVybltpXSwgaSk7CiAgICB9CgogICAgYmZzKCBSb290ICk7CiAgICByZWFkVGV4dCgpOwoKICAgIHJldHVybiAwOwp9Cg==