#2525. 「HAOI2018」字串覆盖

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: dy0607

题目描述

小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 \le n, q \le 10^5 A, B 仅由小写英文字母组成, 1 \le s \le t \le n, 1 \le l \le r \le n, n < K \le 10^9

对于 n = 10^5 的测试点,满足 51 \le r - l \le 2000 的询问不超过 11000 个,且 r - l 在该区间内均匀随机.