A stack is a data type that is a list of elements organized according to the "last in, first out" principle. Most computer system architectures use the stack to call subroutines, as it is best suited for
making the recursion work.
Hardsoft has been developing an innovative processor with a variable length of instruction codes. At the same time, one of its divisions began work on a compiler for the new processor. They managed to create an algorithm for predicting the launch of a particular subroutine based on the source code, and now the developers want to learn based on the information received
determine the optimal stack size.
You need to help them write a program to obtain all possible chains of subroutine calls based on the results of their algorithm.
Input
the first line contains a natural number N, not exceeding 10 - the maximum nesting depth of subroutine calls. Starting from the second line, there is a protocol of operation of the algorithm for predicting the launch of subroutines, which ends with a line, consisting of one dot.
Protocol example:
PROC A
ENDPROC
PROC B
CALL A
ENDPROC
PROC MAIN
CALL B
ENDPROC
.
The description of the subroutine in it begins with the word PROC, after which comes a name from Latin letters, the length of which does not exceed 20 characters.
Inside a subroutine, calls to other subroutines can be indicated using the word CALL and separated by a space - the name of the called subroutine.
The description of the subroutine ends with the word ENDPROC.
Descriptions of subroutines cannot overlap and be nested. The MAIN subroutine is always executed first and is always in the log.
Imprint
in the first line - the number of detected chains, in subsequent lines - call chains corresponding to the original protocol. Each chain must be printed on a new line, and the names of the subroutines in it must be given in the order in which
their calls occur, and are written with a space. The name MAIN should not be displayed, the work of the main subroutine is not included in the call nesting count.
The chains must be output in the order in which they can be called during the execution of the program. Keep in mind that the protocol is designed in such a way that any of the specified calls may or may not take place. However, calling nested subroutines is not possible if the parent subroutine is not called.
Examples
| # |
Input |
Output |
| 1 |
4
PROC A
CALL A
ENDPROC
PROC B
CALL A
ENDPROC
PROC MAIN
CALL B
ENDPROC
. |
4
B
B A
B A A
B A A A |
| 2 |
3
PROC A
CALL A
ENDPROC
PROC B
CALL A
ENDPROC
PROC C
ENDPROC
PROC MAIN
CALL A
CALL B
CALL C
ENDPROC
. |
15
A
A A
A A A
A A B
A C
A B
A B A
A B C
A C
B
B A
B A A
B A C
B C
C |