给定只包含小写字母的字符串 $s,t$（下标从 $1$ 开始）。令 $s[l,r]$ 表示 $s$ 下标从 $l$ 到 $r$ 的子串，类似地定义 $t[l,r]$。
$q$ 次询问给定 $l_1,r_1,l_2,r_2$，询问 $s[l_1,r_1]$ 和 $t[l_2,r_2]$ 的最长公共子序列。
输入格式
输入第一行包含三个整数 $n, m, q$，分别表示 $s$ 串和 $t$ 串的长度与询问次数。
第二行包含一个由小写英文字母组成且长为 $n$ 的字符串 $s$。 第三行包含一个由小写英文字母组成且长为 $m$ 的字符串 $t$。
接下来 $q$ 行，每行四个整数 $l_1, r_1, l_2, r_2$，意义如题目描述。
输出格式
$q$ 行，每行一个正整数表示答案。
样例 #1
输入样例 #1
5 6 7
ababa
abbaaa
3 4 2 2
1 3 2 4
2 5 2 5
1 4 2 5
1 5 1 6
2 5 3 6
2 2 5 6输出样例 #1
1
2
3
2
4
3
0说明
共 10 个 Subtask，每个 Subtask 10 分。
- Subtask 1：$n, m, q \leq 600$；
- Subtask 2,3：$n, m \leq 600，q \leq 10^5$；
- Subtask 4,5：$n, m \leq 3000，q \leq 5000$；
- Subtask 6,7,8,9,10：无特殊限制。
对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 3000，1 \leq q \leq 10^5，1 \leq l_1 \leq r_1 \leq n，1 \leq l_2 \leq r_2 \leq m$。