题目描述

小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在该区间内均匀随机

数据范围