300307: CF59C. Title

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Title

题意翻译

题目描述 Vasya最近写完了一本书。现在他面临着给这本书取一个题目的问题。Vasya希望这本书的标题是含糊而神秘的,来使他的书引人注目。这就是为什么标题应该用至少k个字母中的一个来表示,而不包含任何其他的字母。此外,标题应该是一个回文,也就是说,标题从左到右,从右到左来读是一样的。 Vasya已经写下了标题的近似变体模板。你得到的标题模板由小写字母和问号组成。你的任务是用小写字母替换所有的问号,以使得结果符合上述要求。每个问号应该由一个字母替换,不允许删除字符或者添加新的字符。如果有几个合适的标题,选择字典序最小的标题,帮助Vasya尽可能早地想出标题。 输入输出格式 输入格式: 第一行包含一个整数 k(1 ≤ K ≤ 26),这是允许的字母的数量(译注:如k=2,只有字母a和b可以存在)。第二行是给定的标题模板s,在s中只能有前k个小写字母和问号出现,s的长度可能包含1到100个字符。 输出格式: 如果没有解则输出“IMPOSSIBLE”。否则,输出一行为所需的标题,满足给定的模板。标题应该是一个回文,它只能包含字母表的前k个字母。这样,这k个字母中的每一个至少必须出现一次。如果有几个合适的标题,打印字典序最小的一个。 词典的比较是在现代编程语言标准的<操作符(小于)进行。a在字典序上小于b,如果存在i ( 1≤i≤|s|),那么ai<bi,对于任何的j ( 1≤j<i),aj=bj,其中|s|为给定的模板的长度。 感谢@MarshalKen 提供的翻译

题目描述

Vasya has recently finished writing a book. Now he faces the problem of giving it the title. Vasya wants the title to be vague and mysterious for his book to be noticeable among others. That's why the title should be represented by a single word containing at least once each of the first $ k $ Latin letters and not containing any other ones. Also, the title should be a palindrome, that is it should be read similarly from the left to the right and from the right to the left. Vasya has already composed the approximate variant of the title. You are given the title template $ s $ consisting of lowercase Latin letters and question marks. Your task is to replace all the question marks by lowercase Latin letters so that the resulting word satisfies the requirements, described above. Each question mark should be replaced by exactly one letter, it is not allowed to delete characters or add new ones to the template. If there are several suitable titles, choose the first in the alphabetical order, for Vasya's book to appear as early as possible in all the catalogues.

输入输出格式

输入格式


The first line contains an integer $ k $ ( $ 1<=k<=26 $ ) which is the number of allowed alphabet letters. The second line contains $ s $ which is the given template. In $ s $ only the first $ k $ lowercase letters of Latin alphabet and question marks can be present, the length of $ s $ is from 1 to 100 characters inclusively.

输出格式


If there is no solution, print IMPOSSIBLE. Otherwise, a single line should contain the required title, satisfying the given template. The title should be a palindrome and it can only contain the first $ k $ letters of the Latin alphabet. At that, each of those $ k $ letters must be present at least once. If there are several suitable titles, print the lexicographically minimal one. The lexicographical comparison is performed by the standard < operator in modern programming languages. The line $ a $ is lexicographically smaller than the line $ b $ , if exists such an $ i $ ( $ 1<=i<=|s| $ ), that $ a_{i} < b_{i} $ , and for any $ j $ ( $ 1<=j<i $ ) $ a_{j}=b_{j} $ . $ |s| $ stands for the length of the given template.

输入输出样例

输入样例 #1

3
a?c

输出样例 #1

IMPOSSIBLE

输入样例 #2

2
a??a

输出样例 #2

abba

输入样例 #3

2
?b?a

输出样例 #3

abba

Input

题意翻译

题目描述 Vasya最近写完了一本书。现在他面临着给这本书取一个题目的问题。Vasya希望这本书的标题是含糊而神秘的,来使他的书引人注目。这就是为什么标题应该用至少k个字母中的一个来表示,而不包含任何其他的字母。此外,标题应该是一个回文,也就是说,标题从左到右,从右到左来读是一样的。 Vasya已经写下了标题的近似变体模板。你得到的标题模板由小写字母和问号组成。你的任务是用小写字母替换所有的问号,以使得结果符合上述要求。每个问号应该由一个字母替换,不允许删除字符或者添加新的字符。如果有几个合适的标题,选择字典序最小的标题,帮助Vasya尽可能早地想出标题。 输入输出格式 输入格式: 第一行包含一个整数 k(1 ≤ K ≤ 26),这是允许的字母的数量(译注:如k=2,只有字母a和b可以存在)。第二行是给定的标题模板s,在s中只能有前k个小写字母和问号出现,s的长度可能包含1到100个字符。 输出格式: 如果没有解则输出“IMPOSSIBLE”。否则,输出一行为所需的标题,满足给定的模板。标题应该是一个回文,它只能包含字母表的前k个字母。这样,这k个字母中的每一个至少必须出现一次。如果有几个合适的标题,打印字典序最小的一个。 词典的比较是在现代编程语言标准的<操作符(小于)进行。a在字典序上小于b,如果存在i ( 1≤i≤|s|),那么ai<bi,对于任何的j ( 1≤j<i),aj=bj,其中|s|为给定的模板的长度。 感谢@MarshalKen 提供的翻译

加入题单

上一题 下一题 算法标签: