神牛的养成计划
时间限制：10s 空间限制：512MB
题目描述
Hzwer成功培育出神牛细胞，可最终培育出的生物体却让他大失所望......
后来，他从某同校女神 牛处知道，原来他培育的细胞发生了基因突变，原先决定神牛特征的基因序列都被破坏了，神牛hzwer很生气，但他知道基因突变的低频性，说不定还有以下优秀基因没有突变，那么他就可以用限制性核酸内切酶把它们切出来，然后再构建基因表达载体什么的，后面你懂的......
黄学长现在知道了N个细胞的DNA序列，它们是若干个由小写字母组成的字符串。一个优秀的基因是两个字符串s1和s2,当且仅当s1是某序列的前缀的同时，s2是这个序列的后缀时，hzwer认为这个序列拥有这个优秀基因。
现在黄学长知道了M个优秀基因s1和s2，它们想知道对于给定的优秀基因，有多少个细胞的DNA序列拥有它。
输入格式
第一行：N，表示序列数
接下来N行，每行一个字符串，代表N个DNA序列，它们的总长为L1
接下来一个M，表示询问数
接下来M行，每行两个字符串s1和s2，由一个空格隔开，hzwer希望你能在线回答询问，所以s1等于“s1”的所有字符按字母表的顺序向后移动ans位（字母表是一个环），ans为上一个询问的答案，s2同理。例如ans=2 “s1”=qz
则s1=sb。对于第一个询问，ans=0
s1和s2的总长度为L2
输出格式
输出M行，每行一个数，第i行的数表示有多少个序列拥有第i个优秀基因。
样例输入
10 emikuqihgokuhsywlmqemihhpgijkxdukjfmlqlwrpzgwrwozkmlixyxniutssasrriafu emikuqihgokuookbqaaoyiorpfdetaeduogebnolonaoehthfaypbeiutssasrriafu emikuqihgokuorocifwwymkcyqevdtglszfzgycbgnpomvlzppwrigowekufjwiiaxniutssasrriafu emikuqihgokuorociysgfkzpgnotajcfjctjqgjeeiheqrepbpakmlixyxniutssasrriafu emikuqihgokuorociysgfrhulymdxsqirjrfbngwszuyibuixyxniutssasrriafu emikuqihgokuorguowwiozcgjetmyokqdrqxzigohiutssasrriafu emikuqihgokuorociysgsczejjmlbwhandxqwknutzgdmxtiutssasrriafu emikuqihgokuorociysgvzfcdxdiwdztolopdnboxfvqzfzxtpecxcbrklvtyxniutssasrriafu emikuqihgokuorocsbtlyuosppxuzkjafbhsayenxsdmkmlixyxniutssasrriafu emikuqihgokuorociysgfjvaikktsixmhaasbvnsvmkntgmoygfxypktjxjdkliixyxniutssasrriafu 10 emikuqihgokuorociysg yxniutssasrriafu aiegqmedckgqknky eqpoowonnewbq xfbdnjbazhdnhkhvb qrqgbnmlltlkkbtyn bjfhrnfedlhrlolzfv qppxpoofxcr zhdfpldcbjf stsidponnvnmmdvap zhdfpldcbjfpjmjxdt gdstsidponnvnmmdvap dlhjtphgfnjtnqnbhxr wxwmhtsrrzrqqhzet bjfhrnfedlhrlolzfv frqppxpoofxcr zhdfpldcbjf dponnvnmmdvap ucyakgyxweakehes nondykjiiqihhyqvk
样例输出
4 7 3 5 5 1 3 5 10 4
提示
N<=2000
L1<=2000000
M<=100000
L2<=2000000
题目来源
没有写明来源