삼각행렬

수를 정삼각형 모양으로 늘어놓은 것을 삼각행렬이라고 하자.

크기가 $L$인 삼각행렬은 $L$개의 행으로 이루어지고, 위에서 $i$번째 행에는 수가 $i$개 들어간다.

삼각행렬의 덧셈은 다음과 같이 정의한다.

크기가 같은 두 삼각행렬만 더할 수 있고, 같은 자리에 있는 수끼리 더한다.

삼각행렬의 곱셈은 다음과 같이 정의한다.

곱셈에는 교환법칙이 성립하지 않는다. A * B에서 앞에 오는 $A$의 크기는 $B$의 크기보다 작거나 같아야 한다. $B$ 안에서 $A$와 크기가 같은 삼각형을 모두 찾고, 삼각형마다 겹치는 자리의 수를 곱해서 모두 더한다. 그 합이 결과 삼각행렬의 한 자리를 채운다. 꼭짓점이 $B$의 $r$행 $c$열에 있는 삼각형이 만든 값은 결과의 $r$행 $c$열에 들어간다. 따라서 결과의 크기는 $B$의 크기에서 $A$의 크기를 뺀 값에 1을 더한 것이다.

위 그림에서 $A$와 크기가 같은 $B$ 안의 삼각형은 $\{b_1, b_2, b_3\}$, $\{b_2, b_4, b_5\}$, $\{b_3, b_5, b_6\}$ 세 개다. 대응하는 수끼리 곱해서 더하면 $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$, $e = a_1 b_3 + a_2 b_5 + a_3 b_6$이 된다. $c$를 만든 삼각형이 $B$의 맨 위에 있으므로 $c$는 결과의 맨 위에 놓이고, $d$와 $e$는 원래 삼각형이 놓였던 순서 그대로 다음 행에 $d$가 왼쪽, $e$가 오른쪽으로 놓인다.

식은 후위 표기법으로 주어진다. 예컨대 A B * A +는 (A * B) + A와 같다. 왼쪽부터 차례로 읽으면 A, B, * 순서이므로 A * B를 먼저 계산한다. 이 결과를 $C$라고 하고 A B *를 $C$로 바꾸면 C A +가 남으며, 이는 $C + A$를 뜻한다.

입력은 여러 데이터 집합으로 이루어진다.

각 데이터 집합의 첫 줄에는 식에 쓰이는 삼각행렬의 개수 $N$이 주어진다. 이어서 삼각행렬이 하나씩 주어진다. 삼각행렬은 먼저 식별자 문자열 $K$와 한 변의 길이 $L$이 공백을 사이에 두고 한 줄에 주어지고, 다음 $L$개의 줄에 삼각행렬의 값이 공백으로 구분되어 주어진다. 첫 줄에는 값이 1개, 둘째 줄에는 2개, 셋째 줄에는 3개 있고 $L$번째 줄까지 이렇게 이어진다. 값이 1개인 첫 줄이 삼각형의 꼭대기이고, 값이 $L$개인 $L$번째 줄이 삼각형의 밑변이다.

삼각행렬을 모두 준 다음 줄에는 계산할 식이 주어진다. 식의 연산자와 기호는 공백으로 구분되고, 삼각행렬은 식별자 문자열로 나타낸다.

$N$이 0이면 입력이 끝난다.

데이터 집합마다 식을 계산한 결과 삼각행렬을 입력과 같은 형식으로 출력한다. 첫 줄에 꼭대기 값을 출력하고 다음 줄부터 각 행의 값을 왼쪽부터 공백으로 구분해 출력하며, 마지막 줄에 밑변을 출력한다. 데이터 집합 사이에 빈 줄을 넣지 않는다.

식을 계산할 수 없으면 Invalid expression을 출력한다. 정의되지 않은 식별자가 나오거나, 후위 표기가 올바르지 않거나, 덧셈에서 두 삼각행렬의 크기가 다르거나, 곱셈에서 앞 삼각행렬이 뒤 삼각행렬보다 크면 계산할 수 없다.