I Want to Receive at Least a Special Prize

Interview

Time limit1sMemory limit512 MB

Summary

Given an N x N grid of distinct numbers (N a power of two), recursively pick the second smallest survivor of each quadrant and output the final number.

Level: Medium6 of 10
Topics: Divide and conquer, Recursion, Sorting, Matrix
Solved: No attempts yet

Problem

$N \times N$ people attending HCPC 2021 compete in a hall where the chairs are arranged in a square. Every chair has a distinct raffle number written on it, and at the end of HCPC 2021 one person is chosen to receive a special prize by the rules below.

If exactly one person can receive the special prize, that person is chosen.
Otherwise, the hall is divided into four squares of equal size, and the same rule is applied recursively to each region to choose one person from each, four people in total.
Among the four chosen people, the one whose chair has the second smallest raffle number is chosen.

Jiwon, who attended HCPC 2021, believes his skill is too low to be in prize contention, and he is aiming for the special prize, which he can receive regardless of skill.

See the example below.

Suppose the chairs are arranged as above. Dividing this into four regions gives the following.

Dividing the top-left region of the divided regions into four regions again gives the following.

Choosing the person with the second lowest raffle number here gives the following.

Performing this operation on all regions gives the following.

Thus the raffle number that receives the special prize is as follows.

Therefore, the participant sitting in the chair with raffle number $3$ receives the special prize.

Given the raffle number written on each chair, write a program that computes which chair Jiwon must sit in to receive a prize at HCPC 2021.

Input

The first line gives the integer $N$ . ( $N = 2^m$ , $0 \le m \le 10$ , $m$ is an integer)

From the second line, the $i$ -th of $N$ lines gives the raffle numbers written on the chairs in the $i$ -th row. Each line gives $N$ raffle numbers separated by spaces.

Each raffle number is a nonnegative integer less than $2^{31}$ , and all raffle numbers are guaranteed to be distinct.

Output

Print the raffle number written on the chair Jiwon must sit in to receive a prize at HCPC 2021.

Examples2

Example 1
Input
```
2
2 0
3 1
```
Expected output
```
1
```

Example 2

Input

Expected output