题目描述
小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 = \text{abcbababa}, P = \text{aba})，覆盖加粗部分的子串，收益为 (K - 5 = 6)。
对于第二组询问 (T = \text{cbababab}, P = \text{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) 在该区间内均匀随机。