注意

本题的输入输出格式与原题不尽相同。

题目描述

给定两个 01 串 $S, T\ (|S| = n, |T| = m)$，记 $S_{[l, r]}$ 表示截取 $S$ 的第 $[l, r]$ 个字符得到的子串，对 $q$ 个给定的 $(l, r)$ 求 $S_{[l, r]}$ 与 $T$ 的最长公共子串长度。

输入格式

第一行三个正整数 $n, m, q$。

第二行一个长度为 $n$ 的 01 串 $S$。

第三行一个长度为 $m$ 的 01 串 $T$。

下面 $q$ 行，每行两个正整数 $l, r$。

输出格式

对于每个询问，输出一行一个非负整数表示答案。

样例

4 9 3
0010
000011100
1 4
1 3
2 4

3
3
2

数据范围

• 对于 $10\%$ 的数据，$n, m, q \le 50$。
• 对于 $30\%$ 的数据，$n, m, q \le 2 \times 10^3$。
• 对于另外 $20\%$ 的数据，$q \le 10$。
• 对于 $100\%$ 的数据，$1 \le n, m, q \le 2 \times 10^5$，$1 \le l \le r \le n$。