ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1253. Necrologues

Time limit: 1.0 second
Memory limit: 64 MB
You know that many necrologues even the most heartfelt are very similar. Our partners from the ACM Company (Advanced Cemetery Management), which is a sponsor of today's thematic problem set, decided to disclose some secrets of skill. As soon as we got into the workshop of the word-painters we found out that:
  1. there are N (1 ≤ N ≤ 9) sample necrologues;
  2. each sample necrologue has not more than 1000 symbols (capital and small Latin letters, digits, punctuation marks, spaces and carriage return marks);
  3. each sample may contain not more than 10 references to other samples (the reference is marked by *, which is followed by a number of a sample that is referred to; the *-mark is used in the samples in no other way but as a reference mark).
A reference may be activated at a client's pleasure: the sequence *M is substituted with the sample necrologue number M (with all its references).
This system worked properly up to the moment that a very rich client entered the workshop. He wanted to add a stone to his mother's-in-law cairn and wished a necrologue according to the sample number 1 with all the references activated (including the ones that can appear after activating the references in the first sample, and so on).
It's necessary to write a program in order to understand if it's possible to fulfill the wishes of the client and what will appear in this necrologue.

Input

The first input line contains a number N, an amount of the necrologues samples. Than follow the samples texts. Each samples starts from a new line and ends with the # symbol.

Output

Consider the necrologue forming procedure that starts from the first sample, activates all the references than activates all the references in the result of the previous step and so on ad infinitum. If such a procedure leads to the text not longer than 106 symbols (spaces and line feeds are considered as symbols) you should output the necrologue text. You should output # otherwise.

Sample

inputoutput
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.
Problem Author: Leonid Volkov
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003