B-Forsaken喜欢字符串_牛客小白月赛18

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Forsaken有一堆字符串，他发现每个字符串都有自己的价值。比如说对于一个字符串 $S$ ，长度为 $|S|$ 。如果存在其他字符串 $S_i$ ，长度为 $|S_i|$ 。那么字符串 $S$ 能获得的价值为 $f(i) = \sum_{l_1=1}^{|S|}\sum_{r_1=l_1}^{|S|}\sum_{l_2=1}^{|S_i|}\sum_{r_2=l_2}^{|S_i|}[S[l_1,r_1] =S_i[l_2,r_2]](r_1-l_1+1)$ ， $[S[l_1,r_1] =S_i[l_2,r_2]]$ 是指对于 $S$ 的子串 $[l_1,r_1]$ 与 $S_i$ 的子串 $[l_2,r_2]$ 相等时为1，否则为0。

现在Forsaken有 $n$ 个串并且每个串的长度都是 $k$ ，现在他会问你 $q$ 个问题，对于每个问题，你需要回答对于串 $S_x$ 的所有长度为 $len$ 的子串的价值之和(不包括 $S_i$ 自身的子串)。

输入描述:

第一行两个整数。
接下来行每行一个长度为且都是小写字母的字符串
第行是一个整数。
接下来行每行两个整数。

输出描述:

行整数分别对应每个询问的答案

示例1

输入

复制

3 2
aa
aa
aa
1
3 1

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

备注: