AT_pakencamp_2021_day2_o Golf

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day2/tasks/pakencamp_2021_day2_o 文字列 $ S $ が与えられます。 $ S[i:j] $ で $ S $ の $ i $ 文字目から $ j $ 文字目までを取り出した文字列を表すことにします。 文字列 $ T $ が次の条件を全て満たすとき、 $ T $ は*良い文字列*であると定義します。 - $ 1\ \leq\ |T|\ \leq\ |S| $ - $ S[i:i+|T|-1]\ =\ T $ を満たす整数 $ i $ はちょうど $ 1 $ つだけ存在する 例えば $ S $ が `abcbabc` のとき、 `cb` や `abcb` 、 `abcbabc` は*良い文字列*ですが、 `abc` や `zyx` は*良い文字列*ではありません。 $ Q $ 個のクエリが与えられるので処理してください。 $ i $ 番目のクエリでは $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ |S| $ を満たす整数 $ L_i,\ R_i $ が与えられるので、次の問題の答えを出力してください。 - $ 2 $ つの整数 $ 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\ \,\ (1\ \leq\ i\ \leq\ Q) $ 行目には $ i $ 番目のクエリの答えを出力せよ。

### 制約 - $ S $ は英小文字からなる - $ 1\ \leq\ |S|\ \leq\ 2\ \cdot\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \cdot\ 10^5 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ |S|\ \,\ (1\ \leq\ i\ \leq\ Q) $ ### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ l=2,\ r=4 $ とすると $ r-l+1=3 $ となり、これが最小です。 `bc` は\*良い文字列\*ではないので、 $ l=2,\ r=3 $ とすることはできません。 $ 2 $ 番目のクエリでは、 $ l=2,\ r=5 $ とすると $ r-l+1=4 $ となり、これが最小です。 $ 3 $ 番目のクエリでは、 $ l=1,\ r=7 $ とすると $ r-l+1=7 $ となり、これが最小です。一般に $ S $ そのものは\*良い文字列\*であることに注意してください。 ### Sample Explanation 3 原案: \[Forested\](https://atcoder.jp/users/Forested)