Competitions

# XOR path

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 b1, b2, . . ., b2n−1 are integers, written in the cells that you have visited.

The cost of the path is b1b2 ⊕ . . . ⊕ b2n−1.

Find the path from (1, 1) to (n, n) with minimum cost.

#### Input

First line contains one integer n (2n20) - the size of the matrix.

Each of the next n lines contains n integers ai1, ai2, . . . , ain (1aij109).

#### Output

Print one integer - the lowest possible path price.

#### Note

The expression xy 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».

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
2
1 8
2 8

Output example #1
1

Input example #2
4
99 146 613 1416
513 5810 1515 9616
1247 5124 6284 5844
1139 6135 6427 1561

Output example #2
241

Source 2019-2020 ACM SEERC, 1/4 Finals, Dnepr, Kiyev, Lviv, Mikolayiv, Ternopil, Kharkiv, September 14