Time Limit: 2 sec / Memory Limit: 256 MB
問題文
okayama国の首都ookayamaでは、ookayama
の先頭に1個以上の任意の個数のo
が付加された文字列のことを良い文字列と呼ぶ。
あなたの仕事は文字列Sを次のルールで処理するプログラムを書くことである。
- 手順1. Sの部分文字列に良い文字列が存在するならば手順2へ、存在しないならば処理を終了する。
- 手順2. 良い文字列であるようなSの部分文字列のうち、長さが最長のものを選びこれをTとして手順3へ。最長のものが複数ある場合は最も左側にあるものを選ぶ。
- 手順3. Tに
oo
という部分文字列が存在するならば、そのうち最も左側にあるものをO
へ置換して手順4へ、存在しないならば手順1へ。 - 手順4. Tに
OO
という部分文字列が存在するならば、そのうち最も左側にあるものをo
へ置換する。存在するかどうかにかかわらず手順3へ。
処理終了後のSを求めよ。この処理結果が何に用いられるかは機密情報であるため、あなたは知る必要はない。
ある文字列TがSのi (1 \leq i \leq |S|)文字目からj (i \leq j \leq |S|)文字目までを取り出したものであるとき、TはSの部分文字列であると呼ぶ。ここで | S | は文字列Sの長さを表す。
入力
入力は以下の形式で標準入力から与えられる。
S
1 行目に処理すべき文字列S(1 \leq | S | \leq 100)が与えられる。Sは英小文字のみからなることが保証される。
出力
処理終了後のSを1行に出力せよ。改行を忘れないこと。
入力例1
ooookayama
出力例1
okayama
文字列ooookayama
に対し、処理を行うと、以下のような順序で扱われる。
- 手順1においてSの部分文字列に良い文字列は存在する。
- 手順2において良い文字列であってSの部分文字列であるようなもののうち長さが最長のものは1番目の
o
から始まる部分文字列である、ooookayama
である。これをTとする。 - 手順3においてTに存在する
oo
という部分文字列のうち、最も左側にあるものをO
に置換する。TはOookayama
となる。 - 手順4においてTに
OO
という部分文字列は存在しない。 - 手順3においてTに存在する
oo
という部分文字列のうち、最も左側にあるものをO
に置換する。TはOOkayama
となる。 - 手順4においてTに存在する
OO
という部分文字列のうち、最も左側にあるものをo
に置換する。Tはokayama
となる。 - 手順3においてTに
oo
という部分文字列は存在しない。 - 手順1においてSは
okayama
である。Sの部分文字列に良い文字列は存在しない。処理を終了する。
入力例2
ooookayamaoooookayama
出力例2
okayamaOkayama
Sの部分文字列には、良い文字列が複数存在することもある。最長のものかつ最も左側にあるものから処理する必要があることに注意せよ。また、与えられる入力には英大文字は含まれないものの、答えや処理の過程には現れる可能性があることに注意せよ。
入力例3
okayama
出力例3
okayama
文字列okayama
の部分文字列には良い文字列は存在しない。
入力例4
ookayama
出力例4
ookayama
文字列ookayama
の部分文字列には良い文字列は存在しない。良い文字列とはookayama
の先頭に1個以上の任意の個数のo
が付加された文字列のことであるためookayama
は条件を満たさない。
入力例5
ooookayamakenooooookayamashiookayama
出力例5
okayamakenOokayamashiookayama