Product of matrices P97589


Statement
 

pdf   zip

thehtml

Write a program that, given a sequence of square matrices m1, …, mn, prints in which order the matrices must be multiplied exactly once so that the the result is as big as possible. We consider that the matrices are to be compared in lexicographical order, from top to bottom and from left to right.

Input

Input consists of a natural number n > 0, followed by m1, …, mn. All the matrices have size 2 × 2, and their four elements (natural numbers between 0 and 9) appear in one or more lines.

Output

Print the order in which the matrices must be multiplied exactly once so that the result is maximum, following the format of the examples. If there is more than one way to obtain the same result, choose the lexicographically smallest, comparing the matrices from left to right.

Public test cases

  • Input

    2

1 2
3 4

5 6
7 8

    Output

    5 6 * 1 2 = 23 34
7 8   3 4   31 46

  • Input

    1

3 4
6 7

    Output

    3 4 = 3 4
6 7   6 7

  • Input

    3

9 0 3 3

2 2 0 2

1 1 5 0

    Output

    2 2 * 1 1 * 9 0 = 114 6
0 2   5 0   3 3   90 0

  • Input

    2

3 0 0 3

1 3 0 4

    Output

    1 3 * 3 0 = 3 9
0 4   0 3   0 12
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions