[HAOI2018] 字串覆盖

小C对字符串颇有研究，他觉得传统的字符串匹配太无聊了，于是他想到了这 样一个问题． 对于两个长度为n的串A, B, 小C每次会给出给出4个参数s, t, l, r. 令A从s到t的 子串(从1开始标号)为T，令B从l到r的子串为P.然后他会进行下面的操作： 如果T的某个子串与P相同，我们就可以删掉T的这个子串，并获得K − i的收 益，其中i是初始时A中(注意不是T中)这个子串的起始位置，K是给定的参数． 删除操作可以进行任意多次，你需要输出获得收益的最大值． 注意每次询问都是独立的，即进行一次询问后，删掉的位置会复原．

从文件cover.in中读入数据. 第一行两个整数n, K，表示字符串长度和参数． 接下来一行一个字符串A. 接下来一行一个字符串B. 接下来一行一个整数q，表示询问个数． 接下来q行，每行四个整数s, t, l, r，表示一次询问．

输出到文件cover.out中. 输出q行，每行一个整数，表示一个询问的答案．

10 11
abcbababab
ababcbabab
5
1 9 7 9
3 10 8 10
1 10 1 2
5 7 2 3
1 5 3 6

6
10
22
5
10

样例1解释  子任务 对于所有数据，有 $ 1 ≤ n, q ≤ 10^5 $ ，A, B仅由小写英文字母组成，$ 1 ≤ s ≤ t ≤n $ , $ 1 ≤ l ≤ r ≤ n $ , $ n < K ≤ 10^9 $ ． HAOI2018 round1 T3 对于 $ n = 10^5 $ 的测试点，满足51≤r−l≤2*10^3 的询问不超过11000个，且r−l在该区间内均匀随机 数据范围