← 返回题目列表

Codeforces · 716/B

B. 完成单词

中文机器翻译题面 查看原题

编码员 ZS 喜欢看字典。他认为,如果一个单词存在一个长度为 26 的子串(字母的连续片段),其中英文字母表中的每个字母都恰好出现一次,那么这个单词就是好单词。特别是,如果字符串的长度严格小于 26,则不存在这样的子字符串,因此不太好。

现在,编码员 ZS 告诉你一个单词,其中一些字母由于他忘记而丢失了。他想确定是否可以填写缺失的字母,以便生成一个好的单词。如果可能的话,他也需要你找到这个词的例子。你能帮助他吗?

输入

输入的第一行也是唯一一行包含单个字符串 s (1 ≤ |s| ≤ 50 000),即编码器 ZS 记住的单词。字符串的每个字符都是英文字母的大写字母('A'-'Z')或者是问号('?'),其中问号表示编码者ZS记不住的字母。

输出

如果无法用大写字母替换所有问号以使生成的单词更好,则在唯一的行中打印 - 1。

否则,打印一个字符串,表示编码器 ZS 学到的一个可能的好词。该字符串应与输入中的字符串匹配,但用大写英文字母替换的问号除外。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

ABC??FGHIJK???OPQR?TUVWXY?

输出 #1

ABCDEFGHIJKLMNOPQRZTUVWXYS

输入 #2

WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

输出 #2

-1

输入 #3

??????????????????????????

输出 #3

MNBVCXZLKJHGFDSAQPWOEIRUYT

输入#4

AABCDEFGHIJKLMNOPQRSTUVW??M

输出#4

-1

注意

在第一个示例案例中,ABCDEFGHIJKLMNOPQRZTUVWXYS 是有效答案,因为它包含长度为 26 的子字符串(在本例中为整个字符串),其中包含英文字母表中的所有字母一次。请注意,有许多可能的解决方案,例如 ABCDEFGHIJKLMNOPQRSTUVWXYZ 或 ABCEDFGHIJKLMNOPQRZTUVWXYS。

在第二个示例案例中,没有丢失字母。此外,给定的字符串不存在包含字母表中所有字母的长度为 26 的子字符串,因此答案为 - 1。

在第三个示例案例中,包含英文字母表中所有字母的任何长度为 26 的字符串都适合作为答案。