Inverse X44871


Statement
 

pdf   zip

html

The only way for Neo to escape from the Matrix is to compute its inverse, which will cause the Matrix to cancel itself out. However, the Matrix is large and Neo does not know of any efficient algorithm for computing its inverse. Fortunately, Neo has gained access to the computer mainframe where several backup copies of the Matrix are stored. Neo knows that one of these copies is the inverse of the Matrix, but he does not know which one. Help Neo find the inverse.

Input

The input consists of several test cases. Each test case starts with a number 2≤ n≤ 1000, the dimension of the Matrix. The next n lines contains n integers each, representing the Matrix itself. The next 3n lines also contain n integers each, representing three matrices that are candidates for the inverse.

Output

For each test case, your program must print "1", "2", or "3" on a single line, depending on which of the three candidate matrices corresponds to the inverse of the Matrix.

Observation

Tthe inverse of an n× n matrix M is an n× n matrix M−1 such that M· M−1=In, where In is the n× n identity matrix.

Public test cases

  • Input

    2
1 -2
2 -3
2 -1
1 -3
-3 2
-2 1
2 -3
-1 1

    Output

    2

  • Input

    3
1 -2 2
2 -1 2
2 -2 3
1 2 -2
-2 -1 2
-2 -2 3
2 1 -1
3 2 1
-1 -1 2
1 -1 1
2 -1 -2
3 -2 1

    Output

    1

  • Input

    3
1 2 2
2 1 2
2 2 3
-1 -1 2
2 1 1
3 -2 2
3 -1 -1
-2 2 2
1 -3 1
1 2 -2
2 1 -2
-2 -2 3

    Output

    3
    • Information
    Author
    Anders Jonsson
    Language
    English
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++