Задача Cezar. Над рядком з N літер латинського алфавіту трішки познущалися. Спершу пронумерували усі суфікси від 1 до N, починаючи зліва направо. Наприклад, у рядку “abc” суфікс “abc” - перший, суфікс “bc” - другий, суфікс “c” - третій. Далі відсортували суфікси у алфавітному (лексикографічному) порядку. Після цього усі суфікси замінили на їх номери. Отриману послідовність назвемо характеристичною для цього рядка.
На жаль, початковий рядок було втрачено, але на щастя, залишилась характеристична послідовність і інший рядок з N літер латиниці. Крім того, у вашому розпорядженні наявний шифратор. Цей автомат приймає на вхід два рядки - один з N літер (джерело), інший рівно з 26 літер (ключ). Шифратор заміняє усі входження літери “a” у джерелі на першу літеру з ключа, усі входження літери “b” на другу літеру ключа (загалом усі входження i-тої літери латиниці у джерелі на i-тий символ у ключі). Необхідно віднайти такий ключ з 26 літер, який би у парі з даним в умові джерелом з N літер давав рядок з даною характеристичною послідовністю. При цьому шуканий ключ має бути перестановкою літер латинського алфавіту, тобто кожна літера повинна зустрічатися там рівно один раз.
Технчічні умови. Програма Cezar читає з пристрою стандартного введення натуральне число N (що не перевищує 100000) - кількість символів у вхідному рядку. З другого рядку програма має читати перестановку з N натуральних чисел - характеристичну послідовність. У третьому рядку рівно N маленьких символів латиниці - джерело.
Програма виводить на пристрій стандартного виведення рівно 26 символів латиниці у разі, якщо існує деякий ключ, який міг би у парі з джерелом при перетворенні у шифраторі дав би рядок, характеристична послідовність якої вказана у другому рядку вхідних даних. Якщо таких ключів декілька, виведіть лексикографічно мінімальний. Якщо жодного можливого ключа немає, виведіть IMPOSSIBLE.
|
Введення |
Виведення |
|
3 1 2 3 aaa |
IMPOSSIBLE |
|
Введення |
Виведення |
|
3 1 2 3 cba |
cbadefghijklmnopqrstuvwxyz |
Коментар до другого прикладу: при заміні літера “a” перейде в “c”, літера “b” перейде сама у себе, а літера “c” перейде в літеру “a”. Відповідно, за лексикографічним порядком, “abc” < “bc” < “c”, тобто суфікси відсортовані як 1 2 3.