SGU505 Prefixes and suffixes（询问在线版）
时间限制：20s 空间限制：512MB
题目描述
GAL发现了N个特殊的字母序列，由小写字母组成。小L认为，对于两个字符串s1,s2，若s1是某个特殊序列的前缀，s2是该特殊序列的后缀，则称s1,s2被这个序列拥有。
现在小L给出M对s1,s2，对于每对字符串，问它们被几个特殊序列拥有。
输入格式
第1行一个整数N。
接下来N行，每行一个字符串，代表N个特殊序列。
第N+2行一个整数M。
接下来M行每行一对s1,s2用空格隔开。S1,s2是经过加密的。
设上一问的答案为lastans。解密方法是将s1,s2所有字母向后移动lastans个单位，这时你要把小写字母表当作一个环，比如z的下一个字母是a。
输出格式
对于每次询问操作，输出一个非负整数表示答案。
样例输入
3 aaaaa abacabaa avtobus 6 a a y yy yy y zzzzz zzzz zazb bzaz abac a
样例输出
2 2 1 1 0 1
提示
设N个特殊序列总长为L1，所有M组询问总长为L2。L1，L2<=2000000.N<=2000,M<=100000
题目来源
By Hta