令 s s s 与 w w w 为两字符串，定义：
比如 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 3· · · \n \n · \n · \n · \n · \n · \n · · \n · · \n · · \n
7 3 2\n \n \n
对于 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，字符串由小写英文字母构成。