AT_pakencamp_2021_day2_o Golf

给定一个字符串 $S$。定义子串 $S[i:j]$ 表示从字符串 $S$ 的第 $i$ 个字符到第 $j$ 个字符组成的子串。 如果子串 $T$ 满足以下条件，则称其为一个「好字符串」： - 长度在 1 到 $|S|$ 之间，即 $1 \leq |T| \leq |S|$ - 恰好存在唯一一个整数 $i$，使得 $S[i:i+|T|-1]$ 与 $T$ 相等 例如，若字符串 $S$ 为 `abcbabc`，那么 `cb`、`abcb` 和 `abcbabc` 都是「好字符串」，但 `abc` 和 `zyx` 不是。 接下来有 $Q$ 个查询。对于第 $i$ 个查询，给出两个整数 $L_i$ 和 $R_i$，满足 $1 \leq L_i \leq R_i \leq |S|$，然后解决以下问题： - 寻找两个整数 $l$ 和 $r$，使得 $1 \leq l \leq L_i$ 且 $R_i \leq r \leq |S|$，并使得子串 $S[l:r]$ 是一个「好字符串」。然后计算 $r-l+1$ 的最小可能值。

输入通过标准输入提供，格式如下： > $ S $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

输出 $Q$ 行。对于每个查询，第 $i$ 行输出对应查询的结果。

- 字符串 $S$ 仅由小写英文字母组成。 - $1 \leq |S| \leq 200,000$ - $1 \leq Q \leq 200,000$ - 对于每个 $i$，满足 $1 \leq L_i \leq R_i \leq |S|$ ### 样例解释 对于第一个查询，我们可以取 $l=2, r=4$，此时 $r-l+1=3$，这是最小值。注意 `bc` 不是「好字符串」，所以不能取 $l=2, r=3$。在第二个查询中，取 $l=2, r=5$，得到 $r-l+1=4$，是最小值。在第三个查询中，我们取 $l=1, r=7$，则 $r-l+1=7$，这是最小值。值得注意的是，字符串 $S$ 本身是一个「好字符串」。 **本翻译由 AI 自动生成**