Substring Deletion Maximization Problem

Consider two strings A and B of length n. You are given a fixed integer \(K\). For each query, you are provided with four parameters \(s, t, l, r\). Let \(T\) be the substring of \(A\) from index \(s\) to \(t\) (1-indexed), and let \(P\) be the substring of \(B\) from index \(l\) to \(r\) (1-indexed).

You may perform the following operation any number of times (the operations in each query are independent): If there exists a substring of \(T\) that is exactly equal to \(P\), you can remove that occurrence from \(T\) and obtain a reward of \(K-i\), where \(i\) is the starting position of that occurrence in the original string \(A\) (note that \(i\) is counted with respect to \(A\), not the current \(T\)).

Your task is to select a collection of non-overlapping occurrences of \(P\) in the segment \(A[s \dots t]\) so that the total reward is maximized. Formally, if you choose occurrences starting at positions \(i_1, i_2, \dots, i_k\) satisfying \(s \le i_1 < i_2 < \cdots < i_k \le t-|P|+1\) and \(i_{j+1} \ge i_j+|P|\) for all valid \(j\), then your score will be \(\sum_{j=1}^k (K-i_j)\). Note that if \(K-i_j\) is non-positive, it is better not to choose that occurrence.

Input and Output Restrictions:

• String indices are 1-indexed.
• You are to process multiple queries. Each query is independent, i.e. deletions in one query do not affect the string for another query.
• If no valid occurrence yields a positive reward, the answer is 0.

Note on the Answer Format: Any formulas must be formatted in LaTeX (delimited by \( and \)) as shown above.

inputFormat

The input begins with a line containing two integers \(n\) and \(K\), where \(n\) is the length of the strings \(A\) and \(B\) and \(K\) is the given parameter for reward calculation. The next two lines contain the strings \(A\) and \(B\) respectively, each of length \(n\).

The following line contains a single integer \(Q\), the number of queries. Each of the next \(Q\) lines contains four integers \(s\), \(t\), \(l\), and \(r\) representing a query.

Input Format Summary:

n K
A
B
Q
s t l r
s t l r
... (Q queries)

outputFormat

For each query, output a single integer on a new line indicating the maximum total reward that can be obtained for that query.

sample

10 15
ababaabbab
bababbabba
3
1 10 1 2
2 7 3 5
1 5 4 7

27
12
0