Clarke and expression

Clarke is a patient with multiple personality disorder. One day, Clarke turned into a coder and worked hard. He found type casting in c++ disgusting. If an expression is too long, an error will be extremely likely to be reported due to impossible casting, or a variable will be cast to a not expected type. One day the compiler malfunctioned(doge), so he wanted to complete the compiling work.
Then he left the arduous work to you!
Clarke's expressions are as followings. They are composed of 4 elements:types, variables, brackets and operators, where types and variables are strings consisting of lowercase letters, a bracket is either '(' or ')', and the only operator is '*'. When calculating, we should work from left to right, and deal with brackets first.
Expressions are followed two rules:
1. $type(a)$: meaning casting variable $a$ to type $type$, getting a new variable.($type$ must be a type and $a$ must be a variable. Types and brackets will only appear here in pairs.)
2. $a*b$: meaning casting variable $b$ to the type of variable $a$ and then calculating, getting a new variable of $a$'s type. ($a$ and $b$ must be variables when we are dealing with '*')

Now Clarke will give you an expression, variables and some rules of type casting, and need you to determine whether each expression is legal, and to tell him the type of the result of the expression if it is legal.

Illegal cases:
1. Distinct identifiers of the same name, or variables of nonexistent types.
2. A word neither a type nor a variable.
3. Impossible casting.
4. Expressions not following the rules listed above.

Some explanations and conventions:
1. A variable alone is a legal expression.
2. If $a$ in $type(a)$ is an expression, then get a new variable by calculating $a$ before performing the rule 1.
3. It is possible to cast type $type$ to type $type$.
4. The facts that type $C$ can be cast to type $B$ and that type $B$ can be cast to type $A$ do not mean that type $C$ can be cast to type $A$.
5. Expression $b*type(a)$ means first casting $a$ to type $type$, then casting it to the type of $b$ and finally getting a new variable of the type of $b$.

The first line contains a integer $T(1 \le T \le 10)$, denotes the number of test cases.
For each test case:
The first line contains a integer $n(1 \le n \le 500)$, denotes the number of variables.
Then $n$ lines follow, line $i$ contains two string $value_i, valueType_i$, denote name and type of this variable.
Then a new line contains an integer $m(1 \le m \le 500)$, denotes the number of types.
Then $m$ lines follow, at line $i$, the first string $type_i$ denotes the name of this type, then an integer $k(0 \le k \le m)$ follow, denotes the number of $i$ can cast. Then $k$ number follow, each number $j$ denotes $i$ can cast to type $j$.
The last line of this test case is an expression $E(1 \le |E| \le 500000)$ which only composed of types, variables, brackets and operators.
Assume that $1 \le \sum_{i=1}^{m} |type_i| + \sum_{i=1}^{n} |value_i| \le 200000, 1 \le \sum_{i=1}^{n} |valueType_i| \le 200000$

For each test case, print the type of this expression if this expression is legal. Otherwise print $-1$.

5
2
a char
b int
2
int 0
char 1 1
int(b*a)
2
a char
b int
2
int 0
char 1 1
char(a*b)
2
a char
b int
2
int 1 2
char 1 1
char(a*b)
2
a char
b int
2
int 1 2
char 1 1
char*char(a*b)*((
1
a char
1
char 0
char

int
-1
char
-1
-1

Hint:
case 1: cast $a$ to $b$ first, getting a new variable of type $int$. then this new variable cast to type $int$ again. Finally we get a new variable of type $int$.
case 2: $b$'s type $int$ can not cast to $a$'s type $char$. So print $-1$
case 3: cast $b$ to $a$ first, getting a new variable of type $char$. then this new variable cast to type $char$ again. Finally we get a new variable of type $char$.
case 4: it does't follow the rule "Types and brackets will only appear here in pairs.".
case 5: it does't follow the rule "Types and brackets will only appear here in pairs."

BestCoder Round #56 (div.2)