Given a matrix a of size n * n of integers.
Let the rows of the matrix are numbered from top to bottom from 1 to n, and the columns from left to right from 1 to n. Let
ai,j be the number on intersection of i - th row and j - th column.
You start the way in the cell (1, 1) and can move only down and to the right. The path must be finished in the cell (n, n). Let
b2, . . .,
b2n−1 are integers, written in the cells that you have visited.
The cost of the path is
b2 ⊕ . . . ⊕
Find the path from (1, 1) to (n, n) with minimum cost.
First line contains one integer n (2 ≤ n ≤ 20) - the size of the matrix.
Each of the next n lines contains n integers
ai2, . . . ,
ain (1 ≤
Print one integer - the lowest possible path price.
The expression x ⊕ y means bitwise operation XOR, applied to the numbers x and y. This operation exists in all modern programming languages, for example, in C ++ and Java, it is designated as «ˆ», in Pascal as «xor».
2 1 8 2 8
4 99 146 613 1416 513 5810 1515 9616 1247 5124 6284 5844 1139 6135 6427 1561