A grammar consists of rules
composed by one or more productions and one or more terminal symbols.
In this exercise we suppose that the productions
start with an uppercase letter,
and that the initial production is called *I*.
For instance, the following grammar
generates all the (non empty) correct parenthesizations:

||

I | → | ( ) | | | ( I ) | | | I I |

||

In this example, |( )| is generated by applying the first rule,
*( ( ) )* is generated by applying the second rule and then the first one,
*( ) ( )* is generated by applying the third rule
and then the first one twice, etcetera.

Assume that *lambda* denotes an empty special terminal symbol.
Using this convention,
the following grammar generates all the words that start with *a*
and that contain an even number of *a*s and an odd number of *b*s:

||

I | → | a OO | ||||

OO | → | a EO | | | b OE | ||

OE | → | a EE | | | b OO | ||

EO | → | a OO | | | b EE | ||

EE | → | lambda | | | a OE | | | b EO |

||

Write a program that prints n terms generable with a given grammar. If a production has r rules (numbered from 0 to r − 1), to decide which rule to pick, use a generator of pseudorandom numbers with parameters m, a, b and s, as it is explained in the exercise :

int random(int r, int m, int a, int b, int& s) {
s = (a*s + b)%m;
return s%r;
}

Input

Input starts with a natural number p > 0 that indicates the number of productions. Each production starts with its name and its number of rules r > 0. Each rule is described with a natural number m > 0 followed by m names of productions or terminal symbols.

Input ends with the number n of terms that must be generated, followed by the four natural numbers m, a, b and s that define the generator of pseudorandom numbers.

Output

Print n lines, each one with the term that results after applying the rules indicated by the generator of pseudorandom numbers. Use the productions from left to right inside every rule. Each word must be preceded by a space.

Observation

The first sentence of the third sample output is the literal translation of a Catalan tongue twister.

Public test cases

**Input**

1 I 3 2 ( ) 3 ( I ) 2 I I 8 1007 499 7 400

**Output**

( ( ) ) ( ( ) ) ( ) ( ) ( ) ( ) ( ( ) ) ( ) ( ( ( ) ) ( ) ) ( ( ) )

**Input**

5 I 1 2 a OO OO 2 2 a EO 2 b OE OE 2 2 a EE 2 b OO EO 2 2 a OO 2 b EE EE 3 1 lambda 2 a OE 2 b EO 15 987 297 15 299

**Output**

a b a a a a b b b b b a a a a a a a a b a a a a b b b b b b b a a a a a b a a b a b b b b b a a b b a a b a a b b a b a a a a b a a a b a a b a a a b a b a a b b b a

**Input**

6 Obj 2 1 Sin 1 Plu Sin 2 1 Y 3 Y of Obj Plu 2 1 Z 3 Z of Obj Y 3 2 a court 1 liver 3 a hanged man Z 1 2 sixteen judges I 2 3 Plu eat Obj 3 Sin eats Obj 5 100207 4517 9843 29253

**Output**

sixteen judges of a court eat liver of a hanged man a hanged man eats a hanged man a court of liver eats liver of a hanged man a court eats sixteen judges sixteen judges of sixteen judges eat a court

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions