题目描述

令 $ 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 $。

输出格式

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

样例

input

8 5 3 3
abacdaba
0 2
1 2
0 0
2 2
1 2
dab 1 4
bac 2 3
eeb 1 3

output

7
3
2

数据范围与提示

对于 $ 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 $，字符串由小写英文字母构成。