【题目描述】

小 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 是给定的参数。删除操作可以进行任意多次，你需要输出获得收益的最大值。

注意每次询问都是独立的，即进行一次询问后，删掉的位置会复原。

【输入格式】

第一行两个整数 n,K，表示字符串长度和参数。

接下来一行一个字符串 A。

接下来一行一个字符串 B。

接下来一行一个整数 q，表示询问个数。

接下来 q 行，每行四个整数 s,t,l,r，表示一次询问。

【输出格式】

输出 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

【样例解释】

对于第一组询问 T = abcbababa, P = aba，将加粗部分的子串删去，收益为K−5=6。

对于第二组询问 T = cbababab，P = bab, 收益为 (K−4)+(K−8)=10。

【数据范围与约定】

对于所有数据，有1≤n,q≤10^5,A,B仅由小写英文字母组成，1≤s≤t≤n,1≤l≤r≤n,n<K≤10^9。

对于 n=10^5 的测试点，满足 51≤r−l≤2000 的询问不超过 11000 个，且r−l在该区间内均匀随机。