第一行四个整数 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
7 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，字符串由小写英文字母构成。