A93117.「雅礼集训 2017 Day1」字符串

令 $ s $ 与 $ w $ 为两字符串，下标从 $0$ 开始，定义：

1. $ w[l, r] $ 表示字符串 $ w $ 在区间 $ [l, r] $ 中的子串；
2. $ w $ 在 $ s $ 中出现的频率定义为 $ w $ 在 $ s $ 中出现的次数；
3. $ f(s, w, l, r) $ 表示 $ w[l, r] $ 在 $ s $ 中出现的频率。

比如 $ f(\texttt{ababa}, \texttt{aba}, 0, 2) = 2 $。

现在给定串 $ s $，$ m $ 个区间 $ [l, r] $ 和长度 $ k $，你要回答 $ q $ 个询问，每个询问给你一个长度为 $ k $ 的字符串 $ w $ 和两个整数 $ a, b $，求：

$$\sum\limits_{i = a} ^ b f(s, w, l_i, r_i)$$

第一行四个整数 $ n, m, q, k $，$ n $ 表示 $ s $ 的长度。
接下来一行一个长为 $ n $ 的字符串 $ s $。
接下来 $ m $ 行，每行两个整数表示 $ l_i, r_i $。
接下来 $ q $ 行，每行一个字符串 $ w $，两个整数 $ a, b $。

对于每个询问一行，输出答案。

对于 $ 10% $ 的数据，$ n, m, k, q \leq 10 $；
对于 $ 30% $ 的数据，满足 $ n, m, k, q \leq 10 ^ 2 $；
对于 $ 50% $ 的数据，满足 $ n, m, k, q \leq 10 ^ 4 $；
对于 $ 100% $ 的数据，满足 $ 0 < n, m, k, q \leq 10 ^ 5, \sum |w| \leq 10 ^ 5, 0 \leq l_i, r_i < k, 0 \leq a, b < m $，字符串由小写英文字母构成。