说明

同本题的easy版本描述.

输入格式

同本题的easy版本描述.

输出格式

同本题的easy版本描述.

样例

1
abcbacabccabacbcbcacb
6
abc
cca
ccb
ccc
aac
ccb

10
2
3
0
1
3

提示

T <= 20.

Q <= 20000.

主串长度 <= 100000.

子串长度 <= 100000.

所有询问的子串长度和 <= 100000.