[BJOI2020] 封印

题目背景

注:NOI 2020 北京队选拔赛因不可抗力因素取消,改为按前一年 CSP-S 第二轮成绩选出省队。因为出现同分,为决定最终 A 队名单,举办了加试。本题即为加试题。

题目描述

给出只包含小写字母 $a,b$ 的两个字符串 $s, t$,$q$ 次询问,每次询问 $s[l \dots r]$ 和 $t$ 的最长公共子串长度。

输入输出格式

输入格式


输入共 $q+3$ 行。 第一行一个字符串 $s$。 第二行一个字符串 $t$。 第三行一个整数 $q$。 接下来的 $q$ 行,每行两个整数 $l_i, r_i(1\le l_i \le r_i \le |s|)$,表示一次询问。

输出格式


输出共 $q$ 行。 第 $i$ 行表示 $s[l_i \dots r_i]$ 和 $t$ 的最长公共子串长度。

输入输出样例

输入样例 #1

aaba
aaaabbbaa
3
1 4
1 3
2 4

输出样例 #1

3
3
2

说明

| 测试点编号 | $\vert s\vert , \vert t\vert \le $ | $q\le$ | | :--------: | :------------: | :------------: | | $1$ | $50$ | $50$ | | $2,3$ | $2\times 10^3$ | $2\times 10^3$ | | $4,5$ | $2\times 10^5$ | $10$ | | $6\sim 10$ | $2\times 10^5$ | $2\times 10^5$ |