I. M.M.A
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today in the arena is Seduneon, and he is ready to go through the matrix to reach the final corner $$$(n, n)$$$, squeezing the maximum out of all bitwise ANDs! $$$ \\ $$$ You are given a square matrix of size $$$ n \times n $$$ consisting of non-negative integers. $$$ \\ $$$ Seduneon starts at the top-left corner of the matrix — cell $$$ (1,1) $$$ — and wants to reach the bottom-right corner — cell $$$ (n,n) $$$. $$$ \\ $$$ At each step, he can move either down or right. $$$ \\ $$$ The profit of a path is the bitwise AND of all numbers encountered along the path (including the starting and ending cells). $$$ \\ $$$ Your task is to find the maximum possible profit that Seduneon can obtain by choosing the optimal path.

Input

The first line contains a single integer $$$ n $$$ $$$ (1 \le n \le 1000) $$$ — the size of the matrix. $$$ \\ $$$ The next $$$n$$$ lines each contain $$$n$$$ integers $$$ a_{i,j} $$$ $$$ (0 \le a_{i,j} \le 2^{26}-1) $$$ — the elements of the matrix.

Output

Print a single number — the maximum possible profit (the AND of all numbers along the optimal path from $$$ (1,1) $$$ to $$$ (n,n) $$$ ).

Examples
Input
3
7 3 3
6 3 7
4 4 4
Output
4
Input
5
66969516 62881771 41514568 11972118 43940139
57756114 60816879 60776426 34516231 9491106
59277745 6543967 60776122 62741759 45421615
11938623 3439903 5163738 67108333 65003244
24596084 58055461 47893159 41145539 60652974
Output
60644520