XOR path#9088
You are given an n \times n matrix consisting of integers.
The rows of the matrix are numbered from top to bottom from to , and the columns — from left to right from to . Let a_{i,j} denote the element at the intersection of the -th row and the -th column.
You start your path at cell and can move only down or to the right. The path must end at cell . Let b_1, b_2, \ldots, b_{2n-1} be the sequence of integers contained in the cells you visit along the path, in order.
The cost of the path is defined as b_1 \oplus b_2 \oplus \ldots \oplus b_{2n-1}.
Find a path from to that minimizes the cost.
The first line contains a single integer n~(2 \le n \le 20) — the size of the matrix.
Each of the next lines contains integers a_{i_1}, a_{i_2}, \ldots, a_{i_n}~(1 \le a_{ij} \le 10^9) — the elements of the matrix.
Print a single integer — the minimum possible cost of a path.
Example 1
Example 2
The expression x \oplus y denotes the bitwise XOR operation applied to the numbers and . This operation is supported in all modern programming languages. For example, in C++ and Java it is denoted by ^, and in Pascal by xor.