题目描述

题目译自 PA 2020 Runda 4 Tekstówka

在去年我们在某社交网络的粉丝页上进行的 PA 中，参与者大声地问我们：「题呢？」。今年，我们决定满足您的期望。

给出了由英文小写字母组成的字符串 $s$ 和 $t$。令 $s_{i,j}\ (1\le i\le j\le |s|)$ 表示由 $s$ 的第 $i$ 个到第 $j$ 个（包含两端）字符依次组成的子串。我们也同样定义 $t_{i,j}$。

你的任务是处理 $q$ 次查询。每次查询用四个整数 $i,j,k,l$ 表示，这里 $1\le i\le j\le |s|,1\le k\le l\le |t|$。对于每次查询，你需要输出子串 $s_{i,j}$ 和子串 $s_{k,l}$ 的最长公共子序列。

注：一个字符串的子序列是指一个字符串通过删除一些（可能不删除）字符且不改变剩余字符顺序得到的串。例如，$\texttt{potyczki}$ 的子串可以是 $\texttt{tyki}$ 或 $\texttt{pi}$，但不能是 $\texttt{koty}$。

我们称字符串 $a$ 和 $b$ 的公共子序列为既是 $a$ 的子序列，又是 $b$ 的子序列的子序列。

我们称字符串 $a$ 和 $b$ 的最长公共子序列为 $a$ 和 $b$ 的子序列中最长的一个。

输入格式

输入第一行包含三个整数 $n,m,q\ (1\le n,m\le 3\cdot 10^3,1\le q\le 10^5)$，分别表示 $s$ 串和 $t$ 串的长度与询问次数。

第二行包含一个由小写英文字母组成且长为 $n$ 的字符串 $s$。

第三行包含一个由小写英文字母组成且长为 $m$ 的字符串 $t$。

接下来 $q$ 行，每行四个整数 $i,j,k,l\ (1\le i\le j\le n,1\le k\le l\le m)$，意义如题目描述。

输出格式

输出 $q$ 行，每行一个整数，表示对询问的回答。

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

数据范围与提示

• 对于一些子任务，满足 $n,m,q\le 600$；
• 对于一些其他的子任务，满足 $n,m\le 600$；
• 对于一些其他的子任务，满足 $q\le 5\cdot 10^3$。

对于上述情况，至少有一个子任务满足。