AT_oupc2023_day1_d Han Burger

$ N $ 個の文字あるいは文字列 $ X_1, X_2, \dots, X_N $ をこの順に連結させた文字列を $ X_1 + X_2 + \cdots + X_N $ と表記します。 文字列に対して、バーガー、全バーガー、半バーガーを以下のように定義します。**この定義はE問題と同じです。** - バーガーとは、全バーガーである文字列、および半バーガーである文字列 - 全バーガーとは、あるバーガー $ A $ とある文字 $ c $ に対して、 $ c + A + c $ と書ける文字列、および空文字列 - 半バーガーとは、ある空でないバーガー $ A $ 、 $ B $ に対して、 $ A + B $ と書ける文字列のうち、全バーガーでない文字列 例えば、`abba` や `abbcca` は全バーガー、`aabb` や `abbacc` は半バーガーですが、`abbcbbc` や `ababa` はバーガーではありません。 英小文字からなる文字列 $ S $ に対し、 $ S + T $ が全バーガーとなるような、英小文字からなる文字列 $ T $ が存在するとき、 $ |T| $ が最小である $ T $ のうち辞書順で最小のものを出力してください。そのような $ T $ が存在しないときは `-1` を出力してください。 辞書順とは ? 文字列 $ S = S_1S_2 \cdots S_{|S|} $ が文字列 $ T = T_1T_2 \cdots T_{|T|} $ より **辞書順で小さい** とは、下記の 1. と 2. のどちらかが成り立つことを言います。ここで、 $ |S|, |T| $ はそれぞれ $ S,T $ の長さを表します。 - 1. $ |S| < |T| $ かつ $ S = S_1S_2 \cdots S_{|S|} = T_1T_2 \cdots T_{|S|} $ 。 - 2. ある整数 $ 1 \leq i \leq \min\{|S|, |T|\} $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ S = S_1S_2 \cdots S_{i-1} = T_1T_2 \cdots T_{i-1} $ - $ S_i $ が $ T_i $ よりアルファベット順で小さい文字である。

入力は以下の形式で標準入力から与えられます。 > $ S $

答えを $ 1 $ 行で出力してください。

### 小課題 1. ( $ 1 $ 点) $ S $ は `a` と `b` からなり、 $ |S| \leq 10 $ となる文字列 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ T = $ `aba` とすると、 $ S+T = $ `abccaaba` は全バーガーとなります。 条件を満たす $ T $ は `aba` 以外にも考えられますが、 $ 2 $ 文字以下であるものは存在せず、 $ 3 $ 文字である $ T $ のうち辞書順で最も小さいのは `aba` であるため、`aba` を出力します。 このテストケースは小課題 1 の制約を満たしません。 ### Sample Explanation 2 $ T $ を空文字列にすれば、 $ S+T = $ `abba` は全バーガーとなります。 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 1 \leq |S| \leq 200{,}000 $ - $ S $ は英小文字からなる文字列