题目描述

给定两个字符串 $S$ 和 $T$，下标从 $1$ 开始。

共有 $q$ 次询问，每次询问给定四个整数 $a,b,c,d$，要求计算子串 $S[a\ldots b]$ 与 $T[c\ldots d]$ 的最长公共子序列长度。

输入格式

第一行包含三个正整数 $n,m,q$，分别表示字符串 $S$ 的长度、字符串 $T$ 的长度和询问次数。

第二行包含一个长度为 $n$ 的小写字母字符串 $S$。

第三行包含一个长度为 $m$ 的小写字母字符串 $T$。

接下来 $q$ 行，每行包含四个正整数 $a,b,c,d$，满足 $1 \le a \le b \le n$，$1 \le c \le d \le m$。

注：原 PDF 的输入格式文字中将 $q$ 单独写在第四行，但样例输入首行为 5 6 7。这里按样例整理为第一行输入 $n,m,q$。

输出格式

输出共 $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次询问的答案，即子串 $S[a\ldots b]$ 与 $T[c\ldots d]$ 的最长公共子序列长度。

样例 0

样例 0 输入

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

样例 0 输出

4
2
2
3
3
0
1

数据范围与提示

对于所有数据，保证 $1 \le n,m \le 3000$，$1 \le q \le 10^5$。