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:

- A leaf generates a single sentence which is the label of the node. For example the
node labeled `a' in figure 1 generates the sentence `
`a`'. - An OR node generates the sequence of sentences which is the union of the
sequences generated by its successors. For instance, the sole OR node in figure 1 generates
the sequence of sentences `
`a`', ``b`'. The order of generation (i.e. the order of sentences in the sequence) is the order of the node successors. - An AND node generates sentences computed as the concatenation of the
sentences generated by its successors. If there are
*n*successors the concatenation uses*n*sentences, each generated by a successor. In addition, the concatenation is performed left to right according to the order of the successors. For example, the AND node from figure 1 generates the sequence of sentences ``ab`', ``bb`'. This sequence is computed by appending the sentence generated by the leaf node `b' to each sentence generated by the OR node. Generally, if is the compound index of the*i*-th sentence generated by an AND node with*n*successors, where*i*_{k}is the index of a sentence corresponding to the*k*-th successor, then the sequence of sentences generated by the AND node is in lexicographic ascending order of the compound indexes of its members.

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.

- 1.
- The first line of the graph data contains a positive integer, say
*n*, which is the number of graph nodes. - 2.
- 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

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

where is a positive integer, is the character ``*`' for an AND node or the character ``|`' for an OR node, the is a strictly positive integer, and*succ*_{i},*i*= 0,*m*( ), 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.

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

-1 3 bb ab bb 0