Typing Monkey
-------------
The famous infinite monkey theorem states that a monkey hitting keys 
at random on a keyboard for an infinite amount of time will almost 
surely type a given text, such as the complete works of William 
Shakespeare.

Rather than testing the above theorem, we set up a similar, somewhat 
less ambitious, experiment.  We have a number of different simple 
keyboards.  Each keyboard has an even number of keys.  Of course,
all keys are distinct.  The keys come in pairs.  We specify these
pairs as follows:

{}[]()<>

In this case, { and } form a pair, [ and ] form a pair, etc.
Of each pair, we call the first one the open key and the 
second one the close key.  So { is an open key and } is the
corresponding close key.

The monkey will type a number of lines.  We need your help with
determining whether any of these lines is valid.  Given the 
above specified keyboard, a line is valid if it is part of the
language corresponding to the following grammar:

exp -> empty
    |  exp exp
    |  { exp }
    |  [ exp ]
    |  ( exp )
    |  < exp >
 
For example,
()
{[()]}
{}{}
are valid lines, and
(()
({)}
[[[]]](}
are invalid lines.

Input
-----
The first line specifies the keyboard.
The subsequent lines are the lines typed by the monkey.
A line containing a single * terminates the input.

Note: the input may consist of 10,000 consecutive ()'s.

Output
------
For each line typed by the monkey, output valid or invalid.

Sample input
------------
{}[]()<>
()
{[()]}
(()
{}{}
({)}
[[[]]](}
*

Sample output
-------------
valid
valid
invalid
valid
invalid
invalid