AT_icpc2014summer_day4_f Longest Match

给定一个字符串 $S$ 和 $m$ 次查询，第 $i$ 个查询包含两个字符串 $x_i,y_i$。 对于每个查询，找到字符串 $S$ 中以 $x_i$ 开头并以 $y_i$ 结尾的最长子串。 对于字符串 $S$，$|S|$ 表示 $S$ 的长度。如果存在整数 $i$，使得对于任意 $1 \le j \le |T|$，$T_j = S_{i+j}$，则称字符串 $T$ 是字符串 $S$ 的子串。

输入格式如下。 > $S$ > $m$ > $x_1$ $y_1$ > $x_2$ $y_2$ > $\cdots$ > $x_i$ $y_i$ 第一行给定字符串 $S$。 第二行为查询次数 $m$。 从第三行开始的 $m$ 行中，第 $i$ 行包含两个字符串 $x_i,y_i$，表示一次查询。

> $len_1$ > $len_2$ > $\cdots$ > $len_i$ 输出一共 $m$ 行，第 $i$ 行表示满足第 $i$ 个查询条件的最长子串长度 $len_i$。如果不存在这样的子串，则输出 $0$。

- $1 \le |S| \le 2 \times10^5 $。 - $1 \le m \le 10^5$。 - $1 \le |x_i|,|y_i|$。 - $\sum_{i=1}^m (|x_i|+|y_i|) \le 2 \times 10^5$。 - $S$ 和 $x_i,y_i$ 仅由小写英文字母组成。