#P0896. 问号回文

问号回文

题目描述

给定一个由小写英文字母和问号组成的字符串 SS,1≤∣S∣≤2×1051\le |S|\le 2\times 10^5。每个问号需要被替换成一个小写英文字母,不同问号的替换互不影响。

要求替换后的字符串是回文串,即正序与逆序完全相同。若存在多组合法的替换方案,输出所得回文串中字典序最小的那个。字典序指从左到右逐位比较两个字符串,首次出现不同字符的位置上字符较小者更小。

若无任何替换方案满足要求,输出 -1。

输入格式

输入一行。一个只含小写英文字母和问号 ? 的字符串 SS,行内不含空格,且 1≤∣S∣≤2×1051\le |S|\le 2\times 10^5。

输出格式

输出字典序最小的回文串;若无解,输出 -1。

样例

a?a
aaa
ab
-1
?b??
abba
a?b
-1