Time Limit: 2 Seconds
Memory Limit: 65536 KB
Professor Maple teaches mathematics in a university. He have invented a function
for the purpose of obtaining the operands from an expression. The function named
op(i,e) can be described as follows:
The expression e may be divided into sub-expression(s) by the operator, which
has the lowest priority in the expression. For example, the expression "a*b+b*c+c*d"
should be divided into three sub-expressions "a*b", "b*c"
and "c*d", because the operator "+" has the lowest priority.
The purpose of this function is to extract the ith sub-expression as the result.
So, in the example above, op(2,e)=b*c.
If we regard the sub-expression as the main expression, it might be divided
again and again. Obviously, the dividing process is recursive. As you see, the
following example is much more complex:
Professor Maple is so lazy that he would leave the work to computer rather
than do it himself, when the expression is long and complicated. Of course,
without your program, the computer won't work out the result automatically.
The input file contains several test cases. The last test case in the input
file is followed by a line containing a symbol "*", indicating the
end of the input data. Each test case consists of two parts. The first part
describes the expression, while the second part contains several questions,
which should be calculated according to the expression.
The first line of each test case contains an expression consists of the expression
name, ":=" and the content of the expression. The expression name
is a lowercase. And the content is composed by lowercases and operators "+",
"(", ")", "*" and "^". For example,
here is a valid expression, p:=a^b*c+(d*c)^f*z+b. Among those operators, "("
and ")" have the highest priority. The operator "^" has
a lower priority, and then "*". The priority of the operator "+"
is the lowest.
The second line of each test case contains an integer n indicating n questions
based on the above expression. This is followed by n lines. Each of them contains
the description of one question, which consists of integers. For example, the
question with three integers "2 1 1" describes the function op(1,op(1,op(2,e))).
To compute this function, we have to keep to the following sequence: First,
according to the first integer 2, divide the expression and extract the 2nd
sub-expression. Then, according to the second integer 1, divide the sub-expression
and extract the 1st one. Finally, according to the third integer 1, divide the
outcome again, and extract the result.
For each test case, display the expression name and a colon on the first line.
Then display the result of each question on a line. The layout of the output
is shown in the sample output.
You may assume that all expressions and functions are always valid.
Display a blank line between test cases.
2 1 1
1 2 1
Output for the Sample Input
Source: Asia 2001, Shanghai (Mainland China)