Random Sentence Generator Write the shortest program you can in any language that reads a context-free grammar from and the number of sentences to produce from stdin, and generates that many random sentences from the grammar.

Input  

Input will come in the following format:

n &lt;START&gt;
{"&lt;A&gt;":["as&lt;A&gt;df","0&lt;A&gt;","&lt;B&gt;&lt;C&gt;","A&lt;A&gt;", ...], "&lt;B&gt;":["1&lt;C&gt;1","\&lt;&lt;T&gt;&gt;",...], ...}


n is the number of sentences to generate.  &lt;START&gt; is identifier of the starting nonterminal symbol.

The grammar is enclosed in the {} and is formatted as follows:


Rules are of the form "&lt;S&gt;":[productions].  &lt;S&gt; is the identifier of the nonterminal.


Rules are delimited with commas.
The right-hand side of a rule is a double-quoted string whose first and last characters are "&lt;" and ">", respectively. The remaining character should be in [A-Z] (upper-case alpha).

productions is a comma-delimited list of double-quoted strings, representing productions.  All characters, including whitespace, in the rule are terminal symbols, except those that are enclosed in angle brackets ("&lt;" and "&gt;"), which are non-terminal symbols and will be the left-hand side of another rule.  An open angle bracket may be escaped, but there is no need to escape a close angle bracket.


Productions will not contain newlines or the newline escape sequence.



Output

You should print each generated sentence to stdout with a trailing newline.

Test Cases
5 sets of balanced parentheses:

5 &lt;S&gt;
{"&lt;S&gt;":["&lt;S&gt;&lt;S&gt;", "(&lt;S&gt;)", ""]}


Example result:

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

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


4 postfix arithmetic expressions (note whitespace within strings is significant, whitespace elsewhere is not):

4 &lt;S&gt;
{"&lt;S&gt;":["&lt;N&gt;", "&lt;S&gt; &lt;S&gt; &lt;O&gt;"], "&lt;O&gt;":["+","-","*","/"], "&lt;N&gt;":["&lt;D&gt;&lt;N&gt;", "&lt;D&gt;"],
 "&lt;D&gt;":["1","2","3","4","5","6","7","8","9","0"]}


Example result:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
I felt like doing a little JavaScript.
Also, I cried a little on the inside when I wrote "document.write"

&lt;body&gt;
    &lt;script type='text/javascript'&gt;
    function foo(){
        t=document.getElementById('ta').value.split("\n");
        eval('p='+t[1]);
        t[0]=t[0].split(' ');
        while(t[0][0]--) {
            s=t[0][1]
            while(x=s.match(/&lt;\w+&gt;/)) {
                ps=s;
                s=s.replace(x,p[x][Math.floor(Math.random()*p[x].length)]);
            }
            document.write(s+"&lt;br&gt;");
        }
    }
    &lt;/script&gt;
    &lt;textarea id='ta' cols='80'&gt;&lt;/textarea&gt;
    &lt;button onclick="foo()"&gt;go&lt;/button&gt;
&lt;/body&gt;


Input:

10 &lt;A&gt;
{"&lt;A&gt;":["a&lt;A&gt;b","c&lt;A&gt;d","&lt;B&gt;"],"&lt;B&gt;":["e&lt;C&gt;e"],"&lt;C&gt;":["z","&lt;A&gt;","&lt;B&gt;"]}


Output:

ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed