/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点： 点
問題文
E869120 は、宝物が入ってそうな箱を見つけました。
しかし、これには鍵がかかっており、鍵を開けるためには英小文字からなる文字列 が必要です。
彼は文字列 を見つけ、これは文字列 の 個以上 個以内の文字が ? に置き換わった文字列であることも分かりました。
ただし、文字列 に対して、 を「文字列 の長さ」とします。
そこで、E869120 はヒントとなる紙を見つけました。
- 条件1：文字列 の中に連続する部分文字列として英小文字から成る文字列 が含まれている。
- 条件2： は、条件1を満たす文字列の中で辞書順最小の文字列である。
そのとき、鍵となる文字列 を出力しなさい。
ただし、そのような文字列 が存在しない場合は代わりに UNRESTORABLE と出力しなさい。
制約
- は英小文字と
?から成る - は英小文字から成る
入力
入力は以下の形式で標準入力から与えられる。
出力
鍵となる文字列 を出力しなさい。
ただし、そのような文字列 が存在しない場合は、代わりに UNRESTORABLE と出力しなさい。
入力例 1Copy
?tc???? coder
出力例 1Copy
atcoder
条件1 を満たす文字列は atcoder, btcoder, ctcoder,..., ztcoder の 個がありますが、その中で最も辞書順で小さいものは atcoder なので、atcoder と特定できます。
入力例 2Copy
??p??d?? abc
出力例 2Copy
UNRESTORABLE
条件1を満たすような文字列 が存在しないので、鍵となる文字列 は存在しません。
Score : points
Problem Statement
E869120 found a chest which is likely to contain treasure.
However, the chest is locked. In order to open it, he needs to enter a string consisting of lowercase English letters.
He also found a string , which turns out to be the string with some of its letters (possibly all or none) replaced with ?.
One more thing he found is a sheet of paper with the following facts written on it:
- Condition 1: The string contains a string as a contiguous substring.
- Condition 2: is the lexicographically smallest string among the ones that satisfy Condition 1.
Print the string .
If such a string does not exist, print UNRESTORABLE.
Constraints
- consists of lowercase English letters and
?. - consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
Output
Print the string .
If such a string does not exist, print UNRESTORABLE instead.
Sample Input 1Copy
?tc???? coder
Sample Output 1Copy
atcoder
There are strings that satisfy Condition 1: atcoder, btcoder, ctcoder,..., ztcoder.
Among them, the lexicographically smallest is atcoder, so we can say atcoder.
Sample Input 2Copy
??p??d?? abc
Sample Output 2Copy
UNRESTORABLE
There is no string that satisfies Condition 1, so the string does not exist.