During last year's edition of Potyczki Algorytmiczne, participants on our social media fanpage loudly asked us: "Where is the text problem?". This year, we decided to meet your expectations.

You are given strings $s$ and $t$ consisting of lowercase English letters. Let $s_{i,j}$ (for $1 \le i \le j \le |s|$) denote the substring of $s$ consisting of all characters from the $i$-th to the $j$-th position, inclusive. We define $t_{k,\ell}$ analogously.

Your task is to process $q$ queries. Each query is described by four integers $i, j, k, \ell$, where $1 \le i \le j \le |s|$ and $1 \le k \le \ell \le |t|$. For each such query, you must output the length of the longest common subsequence* of the strings $s_{i,j}$ and $t_{k,\ell}$.

Input

The first line of input contains three integers $n, m$, and $q$ ($1 \le n, m \le 3000, 1 \le q \le 10^5$), representing the length of $s$, the length of $t$, and the number of queries, respectively.

The second line contains the string $s$ of length $n$ consisting of lowercase English letters.

The third line contains the string $t$ of length $m$ consisting of lowercase English letters.

The next $q$ lines each contain four integers $i, j, k$, and $\ell$ ($1 \le i \le j \le n, 1 \le k \le \ell \le m$) as described in the problem statement.

Output

The output should contain $q$ lines, each containing the answer to the corresponding query.

Examples

Input 1

5 6 7
abaab
babbaa
1 5 1 6
1 3 2 4
2 5 2 5
1 4 2 5
2 5 3 6
2 2 5 6
3 4 2 2

Output 1

4
2
2
3
3
0
1

Subtasks

• In some test groups, $n, m, q \le 600$.
• In other test groups, $n, m \le 600$.
• In yet other test groups, $q \le 5000$.

For each of the cases mentioned above, there is at least one such group.

Note

*A subsequence of a word $a$ is any word that can be formed by deleting any (possibly zero or all) characters from $a$ without changing the order of the remaining characters. For example, subsequences of the word potyczki are tyki and pi, but not koty.

A common subsequence of words $a$ and $b$ is a word that is a subsequence of both $a$ and $b$.

The longest common subsequence of words $a$ and $b$ is any word that is a common subsequence of $a$ and $b$ and whose length is as large as possible.