[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行,每行一个整数,表示一个询问的答案.

输入输出样例

输入样例 #1

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

输出样例 #1

6
10
22
5
10

说明

样例1解释 ![](https://cdn.luogu.com.cn/upload/pic/18143.png) 子任务 对于所有数据,有 $ 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在该区间内均匀随机 数据范围 ![](https://cdn.luogu.com.cn/upload/pic/18142.png)