编码员 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 的字符串都适合作为答案。