Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3205.   The Perfect Cow
Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 1116   Accepted Runs: 699    Multiple test files

For the 39th year in a row, Farmer John was named "Dairy Farmer of the Year". The Dairy Association wants him to exhibit his most perfect cow at the upcoming Cow Convention in Herbster, Wisconsin on the frigid shores of Lake Superior.

FJ keeps up with scientific literature and knows that beauty is actually a trend toward the average rather than the existence of some superior trait. Thus, he wants to find his most average cow and share her beauty with the other Dairy Farmers during the weekend of revelry and partying at the convention.

Happily, each of the N*N cows (2 ≤ N ≤ 99; N odd) has her beauty rating (1 ≤ R_ij ≤ 1,000) inscribed on a tag in her ear, just like in this picture.

Cows aren't so good at math, so FJ lines them up into an N x N square. He asks them to find the median cow in each row (the median cow is the one whose beauty number is bigger than or equal to half the cows in her group and also smaller than or equal to half the cows in her group -- the middle number of the group). From those N medians, FJ then finds the median of those numbers and brings that cow to the convention.

Given a set of N x N cows, find the beauty index of the most perfect (average) cow.


* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains N space-separated integers that are the N beauty indices for row i of the cow square


* Line 1: A single integer that is the index of the most perfect cow as described in the task.

Sample Input

1 5 3 9 5
2 5 3 8 1
6 3 5 9 2
8 8 3 3 2
5 4 4 4 4

Sample Output


Source: USACO 2009 March Competition
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz