4659：Liveness Analysis

A program syntax is defined as below:
PROGRAM ::= STATEMENTS end '\n'
STATEMENTS ::= STATEMENT STATEMENTS | epsilon
STATEMENT ::= a [variable] '\n' | u [variable] '\n' | IF-CLAUSE
IF-CLAUSE ::= if '\n' STATEMENTS end '\n' | if '\n' STATEMENTS else '\n' STATEMENTS end '\n'

In which '\n' means the new line character, epsilon means an empty string, [variable] means a variable, which is represented by a number between 1 and n (inclusive). Same numbers denote the same variable.
The program runs as follows:
If the statement is "a [variable]", it assigns the variable a new value;
If the statement if "u [variable]", it uses value of the variable to do something interesting;
If there is an IF-CLAUSE, it is possible that condition of this clause is satisfied or not satisfied.

We only need to do liveness analysis on this program. This is why we do not explicitly write assigned values, what we do with the variables and condition of IF-CLAUSEs.
In this task, there are three kinds of liveness for each of the variables.
1. Live. In one or more paths of this program, value of the variable at the beginning of the program is used.
2. Dead. In all paths of this program, the variable is assigned a new value before any use of this variable.
3. Half-dead. In all paths of this program, value of the variable at the beginning of the program is not used, but in one or more paths, the variable is never assigned a new value.

First line, number of test cases, T.
Following are T test cases. For each test case, the first line is n, number of variables in the program. The following lines is the program.

Number of lines in the input <= 500000

T lines. Each line contains n numbers. If the variable is live, output 1; if the variable is dead, output -1; if the variable is half-dead, output 0.