题目描述

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

• $w[l, r]$ 表示字符串 $w$ 在区间 $[l, r]$ 中的子串；
• $w$ 在 $s$ 中出现的频率定义为 $w$ 在 $s$ 中出现的次数；
• $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$，求：

输入格式

第一行四个整数 $n, m, q, k$，$n$ 表示 $s$ 的长度。
接下来一行一个长为 $n$ 的字符串 $s$。
接下来 $m$ 行，每行两个整数表示 $l_i, r_i$。
接下来 $q$ 行，每行一个字符串 $w$，两个整数 $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

输出：

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