Grammars P45126

Statement

thehtml

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

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 as and an odd number of bs:

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