String Coverage

Little C has done a lot of research on strings and finds traditional string matching too boring, so he came up with the following problem.

For two strings $A$ and $B$ of length $n$, Little C provides 4 parameters $s, t, l, r$ for each query. Let $T$ be the substring of $A$ from $s$ to $t$ (1-indexed), and let $P$ be the substring of $B$ from $l$ to $r$. He then performs the following operation:

If a substring of $T$ is identical to $P$, we can delete this substring from $T$ and gain a profit of $K - i$, where $i$ is the starting position of this substring in the original string $A$ (note: not in $T$), and $K$ is a given parameter. The deletion operation can be performed any number of times. You need to output the maximum profit obtainable.

Note that each query is independent; that is, after a query is performed, the deleted positions are restored.

Input

The first line contains two integers $n$ and $K$, representing the string length and the parameter. The next line contains a string $A$. The next line contains a string $B$. The next line contains an integer $q$, representing the number of queries. The next $q$ lines each contain four integers $s, t, l, r$, representing a query.

Output

Output $q$ lines, each containing one integer representing the answer to the corresponding query.

Examples

Input 1

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

Output 1

6
10
22
5
10

Note

For the first query, $T = \text{abcbababa}$, $P = \text{aba}$. Deleting the bolded substring results in a profit of $K - 5 = 6$. For the second query, $T = \text{cbababab}$, $P = \text{bab}$. The profit is $(K - 4) + (K - 8) = 10$.

Constraints

For all data, $1 \le n, q \le 10^5$, $A$ and $B$ consist only of lowercase English letters, $1 \le s \le t \le n$, $1 \le l \le r \le n$, $n < K \le 10^9$. For test cases where $n = 10^5$, there are no more than 11,000 queries satisfying $51 \le r - l \le 2000$, and $r - l$ is uniformly distributed within this range.