0253. Телефонные номера

Имя входного файла: phone.in
Имя выходного файла: phone.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

У Васи очень много знакомых. Номера их телефонов он записывает в память своего супертелефона jPhone. Однако, свободная память телефона достаточно быстро заканчивается, поэтому Вася придумал способ сокращать телефонные номера. Как известно, номер состоит из цифр, причем некоторые цифры и даже последовательности цифр могут повторяться. Чтобы сократить повторяющуюся последовательность, Вася записывает ее один раз, а после нее в скобках пишет, сколько раз она повторилась. Например, номер 26262626 может быть записан в виде 26(4) или 26(2)26(2). Причем, если количество повторений равно единице, то скобки и единицу Вася может не писать. Поскольку количество повторений не может быть нулем или начинаться с нуля, записи 26(0) и 26(04) некорректны. Кроме того, Вася не всегда учитывает все повторения последовательности, то есть номер 26262626 может быть записан в виде 26(3)26. Также Вася не хочет усложнять процесс распаковки телефонных номеров, поэтому вложенных скобок никогда не делает, то есть конструкция вида 26(2)(2) недопустима.

После вторжения в Васин супертелефон нового супервируса, в Васиных записях пропали все скобки. Теперь Вася хочет узнать, можно ли по оставшейся информации восстановить исходный номер, если известно, что телефонные номера в Васином городе содержат ровно n цифр.

Формат входного файла

В первой строке задано число n – длина номеров в Васином городе (1 ≤ n ≤ 100). Во второй строке задана последовательность цифр без пробелов длиной не более 50 символов – запись в Васином телефоне.

Формат выходного файла

Выведите телефонный номер, если по приведенной записи его можно однозначно восстановить. Если номер восстановить нельзя, выведите "Impossible". Если существует несколько номеров, которые можно сжать до записи в Васином телефоне, выведите "Ambiguous".

Пример:

Примечание: в первом примере после восстановления скобок запись выглядит так: 7(4)0.
phone.inphone.out
5 740 77770
6 0740 077770


Источник: Командное школьное первенство Республики Карелия по программированию, 4 ноября 2007.

Обсудить       Отправить решение



Версия для печати