Задача E. Размещение портала ≡

Условие

Команда разработчиков игры реализовала уровень с достаточно большой картой, разделенной на N секторов. Теперь они хотят на карте разместить портал, через который персонаж игрока попадает на уровень, так, чтобы путешествие в самый удаленный сектор от этого портала заняло минимальное время.

Если в секторе i расположить портал, то путешествие в сектор j займет время a[i,j] + a[j,i] (при этом i не равно j). Помогите команде разработчиков найти такой сектор, путешествие из которого до самого удаленного от него сектора займет минимальное время.

Пусть время путешествия задано массивом целых неотрицательных чисел а, размер которого N×N. Будем считать a[i,i] = 0.

Напишите программу для решения этой задачи!

Формат входных данных

В первой строке вводится число N – количество секторов на карте, 0 < N ≤ 100.

В следующих строках вводятся элементы массива a через пробел построчно, где 0 ≤ a[i,j] ≤ 1000.

Формат выходных данных

В единственной строке выведите единственное целое число – номер сектора, в котором следует расположить портал.

Примеры тестов

3
0 25 36
27 0 29
35 29 0

2