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 a[i,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 b[1]
, b[2]
, . . ., b[2n−1]
are integers, written in the cells that you have visited.
The cost of the path is b[1]
⊕ b[2]
⊕ . . . ⊕ b[2n−1]
.
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 a[i1]
, a[i2]
, . . . , a[in]
(1 ≤ a[ij]
≤ 10^9
).
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».