Problem Description

This problem is translated from PA 2020 Round 4 Tekstówka.

Last year, during the PA held on a fan page of a certain social network, participants loudly asked us: “Where is the problem?”. This year, we decided to meet your expectations.

You are given two strings $s$ and $t$ consisting of lowercase English letters. Let $s_{i,j}\ (1\le i\le j\le |s|)$ denote the substring formed by the $i$-th through the $j$-th characters (inclusive) of $s$ in order. We define $t_{i,j}$ in the same way.

Your task is to process $q$ queries. Each query is given by four integers $i, j, k, l$, where $1\le i\le j\le |s|$ and $1\le k\le l\le |t|$. For each query, output the length of the longest common subsequence of the substring $s_{i,j}$ and the substring $t_{k,l}$.

Note: A subsequence of a string is a string obtained by deleting some (possibly none) characters without changing the order of the remaining characters. For example, subsequences of $\texttt{potyczki}$ can be $\texttt{tyki}$ or $\texttt{pi}$, but cannot be $\texttt{koty}$.

We call a common subsequence of strings $a$ and $b$ a subsequence that is both a subsequence of $a$ and a subsequence of $b$.

We call the longest common subsequence of strings $a$ and $b$ the longest one among all common subsequences of $a$ and $b$.

Input Format

The first line contains three integers $n, m, q$, representing the lengths of strings $s$ and $t$, and the number of queries.

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

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

The next $q$ lines each contain four integers $i, j, k, l$, with the meaning as described above.

Output Format

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

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

4
2
2
3
3
0
1

Hint

Constraints

This problem uses bundled testdata.

• For some subtasks, $n, m, q\le 600$.
• For some other subtasks, $n, m\le 600$.
• For some other subtasks, $q\le 5\times 10^3$.

Among the above cases, at least one subtask is satisfied.

For $100\%$ of the testdata, it is guaranteed that $1\le n, m\le 3\times 10^3$, $1\le q\le 10^5$, $1\le i\le j\le n$, and $1\le k\le l\le m$.

Translated by ChatGPT 5