两位天才正在玩一个游戏。他们有一个填满整数的 $n \times n$ 方格棋盘。玩家轮流进行操作。先手玩家的操作是划掉一行尚未被划掉的行。后手玩家的操作是划掉一列尚未被划掉的列。在每位玩家各进行 $n-1$ 次操作后，恰好会剩下一个数字没有被划掉。先手玩家的目标是最大化这个数字，而后手玩家的目标是最小化这个数字。

给定一个棋盘，确定当两位玩家都采取最优策略时，游戏结束时剩下的那个未被划掉的数字的值。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 50$)，表示棋盘的大小。接下来的 $n$ 行描述棋盘的行：第 $i$ 行包含 $n$ 个整数 $a_{i1}, a_{i2}, \dots, a_{in}$ ($1 \le a_{ij} \le 2500$)，表示第 $i$ 行的数字。

输出格式

输出一个整数，即当两位玩家都采取最优策略时，游戏结束时剩下的那个未被划掉的数字的值。

样例

输入格式 1

3
1 4 9
8 4 2
7 5 7

输出格式 1

5

说明

1 4 9      1 4 9      1 4 9      1 4 9      1 4 9
8 4 2  →   8 4 2  →   8 4 2  →   8 4 2  →   8 4 2
7 5 7      7 5 7      7 5 7      7 5 7      7 5 7

(注：以上示意图展示了划掉行与列的过程，最终剩下的数字为 5)