Sentence Generator 

A grammar of a language is a set of rules which show the way syntactically correct sentences are build in the language. If the number of sentences is finite then these rules can be specified as a directed acyclic AND-OR graph, as that illustrated in figure 1. We assume, by convention, that the AND nodes are marked by `*', the OR nodes are marked by `|' and the leaf nodes are labeled by any printable character different than `*' and `|'. Each node of the graph designates a sequence of sentences. Generally, such a sequence can contain identical members. We say that a node can generate the sequence of sentences it designates as follows:

Figure 1: An AND-OR graph

The sentences generated by the root node of the graph are the sentences of the language whose syntax is described by the graph. The graph from figure 1 describes a language with two sentences `ab' and `bb'.

The sentences designated by a node of the graph can be generated all at once, or incrementally, a number of sentences at a time. The term incrementally means that the sentences generated at a given time are the next sentences which follow from those previously generated. For example, an incremental generator working for the root node of the graph in figure 1 will be able to generate on its first call the sentence `ab' and on its second call the sentence `bb'. By convention, if the sentences the node are exhausted the generator restarts with the first sentence of the node. In the example above for the third call the generator will produce `ab'.

Your problem is to write a program which behaves as an incremental sentence generator. The program reads a graph, as explained below, and then, one at a time, an integer k. Let |k| be the absolute value of k. The program generates the next |k| sentences of the root node of the graph, prints k and, if k > 0, prints the generated sentences. The program continues with a new set of data, if any, when it reads a null value.


The program reads all its data sets from a text input file. The integer from the first line of the file is the number of data sets. Each data set contains a graph description and a sequence of integers which control the sentence generation process for the graph. The graph is read from the input file as follows:
The first line of the graph data contains a positive integer, say n, which is the number of graph nodes.
The next n input lines describe the nodes, a line for each node of the graph. The nodes are numbered from 0 to n-1. The root node is always numbered 0. For a leaf node the input line has the format

\begin{displaymath}node\_number \ node\_symbol

where $node\_number$ is a positive integer and $node\_symbol$ is a character. If the node is an AND or an OR node the input line is

\begin{displaymath}node\_number \ node\_mark \ number\_of\_successors \ succ_0 \dots succ_m

where $node\_number$ is a positive integer, $node\_mark$ is the character `*' for an AND node or the character `|' for an OR node, the $number\_of\_successors$ is a strictly positive integer, and succi, i= 0,m ( $m= number\_of\_successors - 1$), is a positive integer designating the number of a graph node which is a successor of the currently described node.

All the elements of an input line start from the beginning of the line and are separated by single spaces. Moreover, it is known that a graph can have at most 50 nodes, each node with at most 10 successors, and the length of a sentence can be at most 80 characters. In the example below, the first line declares a single data set, the next 5 lines specify the graph from figure 1 and the remaining 3 lines control the sentence generation process.


For each graph read from the input file, the output of the program (on a text file) is as follows: for each integer k, which is read after a graph description, the program outputs k and, if k > 0 the next k sentences of the root node, one sentence on a line. Each sentence starts at the beginning of the line and there are no spaces between the sentence characters. If k < 0 the generated sentences are not printed.

Sample Input 

0 * 2 1 3
1 | 2 2 3
2 a
3 b

Sample Output 


Miguel Revilla