#6031. 「雅礼集训 2017 Day1」字符串
说明
令 s s s 与 w w w 为两字符串，定义：
- w[l,r] w[l, r] w[l,r] 表示字符串 w w w 在区间 [l,r] [l, r] [l,r] 中的子串；
- w w w 在 s s s 中出现的频率定义为w w w 在 s s s 中出现的次数；
- f(s,w,l,r) f(s, w, l, r) f(s,w,l,r) 表示 w[l,r] w[l, r] w[l,r] 在 s s s 中出现的频率。
比如 f(ababa,aba,1,3)=2。
现在给定串 s s s，m m m 个区间 [l,r] [l, r] [l,r] 和长度 k k k，你要回答 q q q 个询问，每个询问给你一个长度为 k k k 的字符串 w w w 和两个整数 a,b a, b a,b，求：
∑i=abf(s,w,li,ri) \sum\limits_{i = a} ^ b f(s, w, l_i, r_i) i=a∑bf(s,w,li,ri)输入格式
第一行四个整数 n,m,q,k n, m, q, k n,m,q,k，n n n 表示 s s s 的长度。
接下来一行一个长为 s s s 的字符串 s s s。
接下来 m m m 行，每行两个整数表示 li,ri l_i, r_i li,ri。
接下来 q q q 行，每行一个字符串 w w w，两个整数 a,b a, b a,b。
输出格式
对于每个询问一行，输出答案。
样例
8 5 3 3
abacdaba
0 2
1 2
0 0
2 2
1 2
dab 1 4
bac 2 3
eeb 1 37
3
2提示
对于 10% 10\% 10% 的数据，n,m,k,q≤10 n, m, k, q \leq 10 n,m,k,q≤10；
对于 30% 30\% 30% 的数据，满足 n,m,k,q≤102 n, m, k, q \leq 10 ^ 2 n,m,k,q≤102；
对于 50% 50\% 50% 的数据，满足 n,m,k,q≤104 n, m, k, q \leq 10 ^ 4 n,m,k,q≤104；
对于 100% 100\% 100% 的数据，满足 n,m,k,q≤105,∑w≤105 n, m, k, q \leq 10 ^ 5, \sum w \leq 10 ^ 5 n,m,k,q≤105,∑w≤105，字符串由小写英文字母构成。