字符串练手题，不算太难。用字符串 $t$ 代指询问的串 $w$。

首先仔细琢磨一下，发现 $kq\le 10^5$，这启发对 $k$ 进行阈值分治，设阈值为 $B$。

对于 $k\ge B$，发现 $q$ 比较小，考虑对于每个询问，直接枚举所有 $i\in[a,b]$ 的 $[l_i,r_i]$ 来计算答案，对 $s$ 建立 SAM，并让 $t$ 的每个前缀 $t_i$ 跑出与 $s$ 子串匹配的最长后缀长度 $w_i$ 以及其对应的状态 $p_i$，若 $t_{l\sim r}$ 在 $s$ 中存在，则满足 $w_r\ge r-l+1$，对于其出现次数，只需要得到 $t_{l\sim r}$ 在 SAM 上对应的位置即可，预处理后缀树的倍增数组，跳到最后一个满足 $len_f\ge r-l+1$ 的 $p_r$ 的祖先 $f$，查询 $f$ 状态对应的 endpos 集合大小即可，预处理即可。

对于 $k<B$，注意到可以直接枚举 $t$ 的所有子串 $t_{l,r}$，并计算这个子串在 $s$ 的出现次数，同时计算区间 $[l,r]$ 在 $[a,b]$ 这个范围内出现多少次。对于前者，固定 $l$ 移动 $r$ 做匹配，匹配失败后面就直接退出，预处理后缀树的 endpos 集合大小即可计算次数，对于后者，拿 vector 存下每个区间在区间序列中出现的位置，然后二分查找计算出现次数即可。

理论复杂度可以做到 $O(n\sqrt{n\log n})$，两个部分都是，不知道能不能做到更优，实测取 $B=500$ 能过