当前没有测试数据。

题目描述

给定一个字符串 $S$ 和 $m$ 个询问，每次询问从下标 $a$，$b$ 开始的两个后缀的最长公共前缀。

格式

输入格式

第一行一个字符串 $S$。

第二行一个整数 $m$，表示询问的个数。

接下来 $m$ 行，每行两个整数 $a$、$b$，表示一次询问。下标从 $1$ 开始。

输出格式

共 $m$ 行，对于每一个询问，输出其答案。

数据样例

10 3
abcabcabcd
1 4
3 9
8 9

6
1
0

数据规模与约定

• 对于 $100\%$ 的数据，$1\leq |S|\leq10^5$，$1\leq m\leq 5\times10^5$。