给定两个由小写英文字母组成的字符串 $s$ 和 $t$。令 $s_{i,j}$（其中 $1 \le i \le j \le |s|$）表示由 $s$ 中从第 $i$ 个字符到第 $j$ 个字符（包含两端）组成的子串。同理定义 $t_{k,\ell}$。

你的任务是处理 $q$ 个查询。每个查询由四个整数 $i, j, k, \ell$ 描述，其中 $1 \le i \le j \le |s|$ 且 $1 \le k \le \ell \le |t|$。对于每个查询，你需要输出字符串 $s_{i,j}$ 和 $t_{k,\ell}$ 的最长公共子序列（Longest Common Subsequence, LCS）的长度。

输入格式

第一行包含三个整数 $n, m, q$（$1 \le n, m \le 3000, 1 \le q \le 10^5$），分别表示 $s$ 的长度、 $t$ 的长度以及查询的数量。

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

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

接下来的 $q$ 行，每行包含四个整数 $i, j, k, \ell$（$1 \le i \le j \le n, 1 \le k \le \ell \le m$），含义如题所述。

输出格式

输出 $q$ 行，每行包含对应查询的答案。

样例

输入 1

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

输出 1

4
2
2
3
3
0
1

子任务

• 在部分测试点中，$n, m, q \le 600$。
• 在部分测试点中，$n, m \le 600$。
• 在部分测试点中，$q \le 5000$。

对于上述每种情况，至少存在一个对应的测试组。

说明

• 字符串 $a$ 的子序列是指通过删除 $a$ 中的任意（可能为零个或全部）字符，且不改变剩余字符的相对顺序所得到的字符串。例如，potyczki 的子序列包括 tyki 和 pi，但不包括 koty。
• 字符串 $a$ 和 $b$ 的公共子序列是指既是 $a$ 的子序列又是 $b$ 的子序列的字符串。
• 字符串 $a$ 和 $b$ 的最长公共子序列是指长度最大的公共子序列。