Pufňa je strapatá klamara. Sely neustále s neopísateľne dlhým vyplazeným jazykom závistlivo hľadí na Pufnine odstávajúce štice. Uvedomila si pritom grandióznu skutočnosť. Jeden z vlasov je totiž najježatejší. No a v niektorých prefixoch $P$ najježatejšieho vlasu existuje prefix, ktorý je zároveň suffixom tohto prefixu $P$. Sely by pre niektoré prefixy $P$ zaujímalo, aký najdlhší vlastný prefix prefixu $P$ je zároveň suffixom prefixu $P$. Vlastný prefix stringu $S$ je taký, ktorý nie je celé $S$.
Sely je však pahltná psica a odpovede ohľadom prefixov jej nestačia. Okrem najježatejšieho vlasu má Pufňa ďalších najviac 10 menej ježatých. Tu si Sely všimla ďalšiu, tentokrát však kolosálnu skutočnosť. Niektoré úseky najježatejšieho vlasu sú úplne rovnaké, ako niektoré celé menej ježaté vlasy. Sely by sa chcela Pufni posmiať kvôli bagateľnej variabilite jej ježín. Na to však nevyhnutne potrebuje o každom menej ježatom vlase vedieť, koľkrát sa vyskytuje ako substring v najježatejšom vlase.
Nazvime najježatejší vlas $S$. Sely sa bude pýtať otázky dvoch typov:
PVSYVSS yDNVPKJZSVRPDXSS xOdpoveďou na prvý typ otázky je počet výskytov stringu $y$ v stringu $S$. String $y$ tu teda predstavuje nejaký menej ježatý vlas. Týchto otázok bude najviac $10$. Odpoveďou na druhý typ otázky je dĺžka najdlhšieho vlastného prefixu, ktorý je zároveň suffixom v rámci prefixu dĺžky $x$ stringu $S$. Sely vôbec nevadí, ak sa suffix a prefix prekrývajú.
Na prvom riadku je string $S$ - najježatejší vlas. Platí, že $2 \leq |S| \leq 10^5$. Na druhom riadku je číslo $q$ - počet otázok Sely $(1 \leq q \leq 10^5)$. Nasleduje $q$ riadkov. Každý predstavuje jednu otázku vo formáte popísanom v časti úloha. Pre každý menej ježatý vlas $y$ platí, že $1 \leq |y| \leq 10^5$.
Pre každú otázku vypíšte jeden riadok s jedným číslom - odpoveďou na danú otázku. V $i$-tom riadku teda bude odpoveď na $i$-tu otázku.
abcabcd
4
PVSYVSS bc
PVSYVSS lem
DNVPKJZSVRPDXSS 6
DNVPKJZSVRPDXSS 4
2
0
3
1