{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/SEPT16/mandarin/LEXOPAL.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/SEPT16/russian/LEXOPAL.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/SEPT16/vietnamese/LEXOPAL.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\n\u003cp\u003eChef likes strings a lot but he likes palindromic strings even more. Today he found an old string \u003cb\u003es\u003c/b\u003e in his garage. The string is so old that some of its characters have faded and are unidentifiable now. Faded characters in the string are represented by \u0027.\u0027 whereas other characters are lower case Latin alphabets i.e [\u0027a\u0027-\u0027z\u0027].\u003c/p\u003e\u003cp\u003e\n\n\u003c/p\u003e\u003cp\u003eChef being the palindrome lover decided to construct the lexicographically smallest palindrome by filling each of the faded character (\u0027.\u0027) with a lower case Latin alphabet. Can you please help him completing the task?\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eFirst line of input contains a single integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. \u003cb\u003eT\u003c/b\u003e test cases follow.\u003c/p\u003e\n\u003cp\u003eFirst and the only line of each case contains string \u003cb\u003es\u003c/b\u003e denoting the old string that chef has found in his garage.\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case, print lexicographically smallest palindrome after filling each faded character - if it possible to construct one. Print -1 otherwise.\u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\u003cli\u003e\u003cb\u003e1 ≤ T ≤ 50\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ |s| ≤ 12345\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003eString \u003cb\u003es\u003c/b\u003e consists of [\u0027a\u0027-\u0027z\u0027] and \u0027.\u0027 only.\u003c/li\u003e\n\u003c/ul\u003e\u003ch3\u003eSubtasks\u003c/h3\u003e\n\u003cb\u003eSubtask #1 (47 points)\u003c/b\u003e\n\u003cul\u003e\u003cli\u003e\u003cb\u003e1 ≤ T ≤ 50, 1 ≤ |S| ≤ 123\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\u003cb\u003eSubtask #2 (53 points)\u003c/b\u003e\n\u003cul\u003e\u003cli\u003e\u003cb\u003e1 ≤ T ≤ 50, 1 ≤ |S| ≤ 12345\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\na.ba\ncb.bc\na.b\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eabba\ncbabc\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e\u003cb\u003eIn example 1\u003c/b\u003e, you can create a palindrome by filling the faded character by \u0027b\u0027.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eIn example 2\u003c/b\u003e, you can replace the faded character by any character from \u0027a\u0027 to \u0027z\u0027. We fill it by \u0027a\u0027, as it will generate the lexicographically smallest palindrome.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eIn example 3\u003c/b\u003e, it is not possible to make the string \u003cb\u003es\u003c/b\u003e a palindrome.\u003c/p\u003e"}}]}