Triangular Matrices

A triangular matrix is a set of numbers laid out as an equilateral triangle.

A triangular matrix of size $L$ has $L$ rows, and the $i$th row from the top holds $i$ numbers.

Addition of triangular matrices is defined like this.

Only two triangular matrices of the same size can be added, and numbers in matching positions are added together.

Multiplication of triangular matrices is defined like this.

Multiplication is not commutative. In A * B the size of the first matrix $A$ must be less than or equal to the size of $B$. Find every triangle inside $B$ that has the same size as $A$, and for each one multiply the overlapping numbers and add the products. That sum fills one position of the result. The triangle whose apex sits at row $r$, column $c$ of $B$ gives the value at row $r$, column $c$ of the result, so the result has size (size of $B$) minus (size of $A$) plus 1.

In the picture above, the triangles inside $B$ that have the same size as $A$ are $\{b_1, b_2, b_3\}$, $\{b_2, b_4, b_5\}$ and $\{b_3, b_5, b_6\}$. Multiplying the corresponding numbers and adding them gives $c = a_1 b_1 + a_2 b_2 + a_3 b_3$, $d = a_1 b_2 + a_2 b_4 + a_3 b_5$ and $e = a_1 b_3 + a_2 b_5 + a_3 b_6$. The triangle behind $c$ is at the top of $B$, so $c$ takes the top position of the result. $d$ and $e$ go on the next row with $d$ on the left and $e$ on the right, the way the original triangles were arranged.

The expression is given in postfix notation. For instance A B * A + means (A * B) + A. Reading from the left you get A, then B, then *, so A * B is computed first. Call that result $C$ and replace A B * with $C$. What is left is C A +, which means $C + A$.

The input holds several data sets.

The first line of a data set has an integer $N$, the number of triangular matrices used in the expression. The matrices follow, one after another. A matrix starts with a line holding a string identifier $K$ and the side length $L$, then $L$ lines hold the values of the matrix separated by spaces. The first line has 1 value, the second line has 2 values, the third line has 3 values, and so on through the $L$th line. The first line with one value is the top point of the triangle, and the $L$th line with $L$ values is the bottom of the triangle.

After all matrices comes a line with the expression to evaluate. Operators and symbols in the expression are separated by spaces, and each matrix is written as its string identifier.

The input ends when $N$ is 0.

For each data set, print the resulting triangular matrix in the same format the matrices were given in. The top value goes on the first line, then each row from left to right with values separated by single spaces, down to the bottom row on the last line. Do not print a blank line between data sets.

If the expression cannot be evaluated, print Invalid expression. An expression cannot be evaluated when it uses an identifier that was never defined, when the postfix notation is malformed, when addition gets two triangular matrices of different sizes, or when multiplication gets a first matrix larger than the second one.