「PA 2020」Tekstówka

题目描述

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

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

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

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

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

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

输入格式

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

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

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

接下来 $q$ 行，每行四个整数 $i, j, k, l$ ($1 \leq i \leq j \leq n, 1 \leq k \leq l \leq 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 \leq 600$； 对于一些其他的子任务，满足 $n, m \leq 600$； 对于一些其他的子任务，满足 $q \leq 5 \cdot 10^3$。 对于上述情况，至少有一个子任务满足。