AT_jag2017summer_day1_f 極小部分列

[problemUrl]: https://atcoder.jp/contests/jag2017summer-day1/tasks/jag2017summer_day1_f 文字列 $ S $ と $ Q $ 個のクエリが与えらます。 $ i $ 番目のクエリでは文字列 $ T_i $ が与えられるので、$ T_i $ を部分列として含むような $ S $ の極小な部分文字列のうち最も左にあるものを求めてください。 ただし文字列 $ s $ が極小であるとは、$ s $ の部分文字列であって $ T_i $ を部分列として含むような $ s $ より短いものが存在しないことを指すものとします。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ Q $ $ T_1 $ $ T_2 $ $ : $ $ T_Q $

$ i $ 番目のクエリの答えの文字列が $ S $ の $ l $ 文字目から $ r $ 文字目までの部分文字列であるとき、$ i $ 行目に $ l,r $ を空白区切りで出力せよ。ただし、$ S $ が $ T_i $ を部分列として含まない場合は代わりに `-1` を $ i $ 行目に出力せよ。

### 制約 - $ 1≦|S|≦10^5 $ - $ 1≦Q≦10^5 $ - $ 1≦|T_i| $ - $ |T_i| $ の和は $ 10^5 $ を越えない - $ S,\ T_i $ は小文字アルファベットのみからなる ### Sample Explanation 1 $ 1 $ 番目のクエリについて説明します。 答えは $ 2 $ 文字目から $ 4 $ 文字目までの部分文字列 `axb` となります。 他にも $ 5 $ 文字目から $ 6 $ 文字目までの部分文字列 `ab` も $ T_1 $ を部分列として含む極小な部分文字列ですが、`axb` の方が左にあるためこちらは答えとはなりません。 また、`aaxb` は極小ではありません。 なぜなら `axb` という $ T_i $ を部分列として含むような部分文字列を含むためです。