The Perfect Cow

For yet another year, Farmer John was named "Dairy Farmer of the Year". He wants to exhibit his most perfect cow at the upcoming Cow Convention.

According to the scientific literature, beauty is a trend toward the average rather than the existence of some superior trait. So Farmer John wants to find his most average cow and bring her to the convention.

Each cow has her beauty rating $R_{ij}$ ($1 \le R_{ij} \le 1000$) inscribed on a tag in her ear. Farmer John lines the cows up into an $N \times N$ square ($2 \le N \le 99$, and $N$ is odd).

He first finds the median cow in each row. The median cow is the one whose beauty rating is greater than or equal to half of the cows in her row and also less than or equal to half of them — that is, the middle value when the row is sorted. From those $N$ medians he then takes the median again, and that value is the beauty rating of the most perfect (average) cow.

Given the $N \times N$ cows, find the beauty rating of the most perfect cow.

• Line 1: A single integer $N$.
• Lines 2..N+1: Line $i+1$ contains $N$ space-separated integers, the $N$ beauty ratings for row $i$ of the cow square.

• Line 1: A single integer, the beauty rating of the most perfect cow as described above.

In the example, the medians of the rows are, respectively, $5, 3, 5, 3,$ and $4$. The median of those five values is $4$.