Smallest Palindromic Replacement

You are given an integer n and a string s of length n that consists of lowercase letters and the character '?'. Your task is to replace each '?' in the string with a lowercase letter such that the resulting string is a palindrome. Among all possible palindromes, you must output the lexicographically smallest one.

If it is not possible to form a palindrome by replacing the '?' characters, output -1.

The lexicographical order is the usual dictionary order. A string x is lexicographically smaller than a string y if at the first position where they differ, the character in x comes before the character in y in the alphabet.

Note on Input/Output: For this problem, input is given via standard input (stdin) and output must be written to standard output (stdout).

The problem can be formally expressed in LaTeX as:

$$\text{Given } n \in \mathbb{N} \text{ and } s \in \{a, b, \dots, z, ?\}^n, \text{ find the lexicographically smallest palindrome } p \text{ such that } p_i = s_i \text{ if } s_i \neq '?' $$

or output -1 if no such palindrome exists.

inputFormat

The input consists of two lines:

• The first line contains an integer n, the length of the string.
• The second line contains the string s of length n which includes only lowercase letters and the character '?' .

outputFormat

Output a single line containing the lexicographically smallest palindrome formed by replacing each '?' appropriately. If it is impossible to form such a palindrome, output -1.

## sample

5
a?b?a

aabaa