|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
An organization chart depicts the structure of the organization. The figure below shows an example of an organization chart.
As you see, an organization chart is considered as a kind of tree. Each edge represents the relationship of a boss and a subordinate, and hence the depth of each node implies the person’s position in the organization. Relative position of nodes is also often important; for example, when A and B come just under C, it is important which is placed on the left.
One day, a president passed copies of the organization chart of his company to the two officers X and Y, and ordered them to make sequences from the chart in their own ways.
The officer X makes a sequence by tracing edges from right to left, that is, by reverse pre-order traversal. For example, he makes the following sequence from the chart shown above: F, G, H, C, A, E, I, B, J, D.
The officer Y makes another sequence in the order of the levels of the persons. The level of a person is simply measured by his/her depth from the top. As breadth first search, the person of the highest level comes first, while the person of the lowest level comes last. Persons on the equivalent level are ordered from left to right.
The other day, the president has lost the organization chart and all its copies for some reason. But fortunately, he found the sequences made by the officers X and Y, which is enough to reproduce the chart.
Now you are requested to write a program that restructures the organization chart from given two sequences.
Input consists of some data sets. The first line of each set contains a positive integer n (n ≤ 26) that represents the number of persons in the organization. It is followed by two lines that denote the sequence by the officers X and Y respectively, each containing n capital letters from A to Z separated by space.
The end of input is indicated by n = 0, which should not be processed.
For each set, you should output a line that describes the structure of the organization chart. You should output “a(bcd)” if the person a is a boss of the persons b, c and d appearing in this order from left to right in the chart. See samples below for the precise format.
5 A B D C E A B C D E 10 F G H C A E I B J D F B G D J A C H I E 0