#D306. 复原字符串

复原字符串

题目描述:

童童是一个考古爱好者,在去E国旅游的时候,在一个古老的城堡中发现了一串字符,这串字符有些字母已经看不太清楚了。童童猜测这串字符有可能是一个回文串。回文串的定义:就是一个从左到右读、从右到左读都一样的字符串。比如 “ABCBA”、“ABBA”、“AXA” 都是回文串,而 “ABCD”、“ABDBDA” 则不是回文串。 童童希望学编程的你能够帮助他编程实现:如果确定不是一个回文串或者不能复原成一个唯一的回文串,就输出"IMPOSSIBLE"。反之能够确定复原成一个唯一的回文串,就输出这个回文串。例如:ABA00可以复原成一个唯一的回文串ABABA。ABC0CDD,这根本不可能是一个回文串,因此就输出"IMPOSSIBLE"。

输入格式:

第1行包含一个正整数 n,代表童童看到的字符串的长度。 第2行包含一个字符串,仅由大写字母和 "0" 组成,"0" 表示童童看不清的字母。

输出格式:

输出仅一行,如果能够确定复原成唯一的回文串,就输出还原后的回文串,否则输出 ”IMPOSSIBLE“。

样例1:

5
AB0BA
IMPOSSIBLE

样例2:

6
BB0A00
BBAABB

提示

对于 100% 的数据,n≤10^5。