E. Некрологи @ Соревнование команд УрГУ. Март 2003 @ Timus Online Judge

E. Некрологи

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вы знаете, что многие, даже самые прочувствованные некрологи, почему-то напоминают друг друга как две капли воды. Приоткрыть завесу тайны, поделиться секретами мастерства решили наши партнеры из компании ACM (Advanced Cemetery Management), которая, как известно, выступает спонсором нынешнего тематического комплекта. Проникнув в мастерскую художников, мы обнаружили что

имеется N (1 ≤ N ≤ 9) заготовок некрологов;
в каждой заготовке не более 1000 символов (прописных и строчных букв латинского алфавита, цифр, знаков препинания, пробелов, переводов строки);
каждая из заготовок может содержать в своем тексте до 10 ссылок на другие заготовки (ссылка отмечается знаком *, за которым следует номер заготовки, на которую идет ссылка; знак * не используется в тексте заготовки как-либо, кроме как для обозначения ссылки).

По желанию клиента (и за дополнительную плату), ссылка может быть активирована: последовательность символов *M заменяется текстом заготовки (вместе с ее ссылками), носящей номер M.

Такая система работала превосходно, пока в мастерской не объявился очень богатый клиент. Желая наилучшим образом воздать память своей теще, он попросил изготовить некролог по заготовке номер 1, активировав все ссылки, в том числе и те, которые могут появиться при активации ссылок в первой заготовке и так далее.

Чтобы понять, удастся ли удовлетворить желание клиента, и что получится в результате изготовления такого некролога, придется срочно написать программу…

Исходные данные

Первая строка входа содержит число N, количество заготовок некрологов, имеющихся в наличии. Далее следуют тексты заготовок; каждая заготовка начинается с новой строки, а заканчивается символом #. Заготовки считаются занумерованными в соответствии с порядком их появления на входе.

Результат

Представим себе процедуру формирования некролога, которая начинает с первой заготовки, активирует все ссылки, затем снова активирует все ссылки в том, что получилось, и так далее до бесконечности. Если такая процедура приведет к формированию текста некролога, имеющего длину не более 10⁶ символов (пробелы и переводы строк также считаются символами), то на выход следует подать точный текст получающегося некролога. В противном случае в выход надо записать единственный символ #.

Пример

исходные данные

результат

7
She w*7s *7 *2 wom*7n.
*3#
wonderful#
Everyone loved her *5.
We will miss her *5.#
Some text *6#
very much#
Another text *4#
a#

She was a wonderful woman.
Everyone loved her very much.
We will miss her very much.

Автор задачи: Леонид Волков
Источник задачи: Open collegiate programming contest for student teams, Ural State University, March 15, 2003