This page is still under construction.

Parts of this page are still being built. What you see may change.

Matrix Multiplication Calculator

Time limit2sMemory limit512 MB

Summary
Read pairs of matrices with dimension lines, multiply them when the inner dimensions match, and print each result row wrapped in vertical bars, or print undefined.
Level

Easy2 of 10

Topics
Implementation, Matrix, Math, Brute force
Solved
No attempts yet

Problem

Matrix multiplication is a basic operation of linear algebra, with applications across mathematics, applied mathematics, computer graphics, physics, and engineering.

Two matrices can be multiplied only when their dimensions are compatible: the number of columns of the first matrix must equal the number of rows of the second matrix.

If A=[aij]A = [a_{ij}] is an m×nm \times n matrix and B=[bij]B = [b_{ij}] is an n×qn \times q matrix, the product ABAB is an m×qm \times q matrix. The product ABAB is defined as the m×qm \times q matrix C=[cij]C = [c_{ij}] with

cij=∑k=1naikbkjc_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}

Build a matrix multiplication calculator that multiplies two given matrices and prints the result. If the matrices cannot be multiplied, print undefined.

Input

The input consists of several test cases. For each test case, the first line gives four positive integers M,N,P,QM, N, P, Q (1≤M,N,P,Q≤201 \le M, N, P, Q \le 20). MM and NN are the dimensions of matrix AA, while PP and QQ are the dimensions of matrix BB. The next MM lines hold matrix AA, followed by PP lines holding matrix BB. Each row lists its entries separated by single spaces. The input ends with a line 0 0 0 0, which is not processed.

Output

For each test case, print a line Case #x:, where xx is the case number starting from 11. On the following lines, print the result of the multiplication. When the product exists, print one row of the result matrix per line in the form | entries |, wrapped in | characters with entries separated by single spaces. When the matrices cannot be multiplied, print a single line undefined.

Examples1

  1. Example 1

    Input
    2 3 3 2
    1 2 3
    3 2 1
    4 5
    6 7
    8 9
    2 3 2 3
    1 2 3
    3 2 1
    4 5 6
    7 8 9
    0 0 0 0
    
    Expected output
    Case #1:
    | 40 46 |
    | 32 38 |
    Case #2:
    undefined