P4493 [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$ 是给定的参数。一个位置不能被覆盖多次．覆盖操作可以进行任意多次，你需要输出获得收益的最大值。 注意每次询问都是独立的，即进行一次询问后，覆盖的位置会复原。

第一行两个整数 $n,K$ 表示字符串长度和参数。 接下来一行一个字符串 $A$。 接下来一行一个字符串 $B$。 接下来一行一个整数 $q$，表示询问个数。 接下来 $q$ 行，每行四个整数 $s,t,l,r$ 表示一次询问。

输出 $q$ 行，每行一个整数，表示一个询问的答案．

样例 $1$ 解释  对于所有数据，有 $1\le n,q\le 10^5$，$A,B$ 仅由小写英文字母组成，$ 1\le s\le t\le n$，$ 1\le l\le r\le n$，$n