Однажды граф Уильям Гамильтон решил совершить кругосветное путешествие, в котором он посетил бы N крупнейших городов Земли. Между всеми парами городов есть дороги. Каждой дороге, ведущей от одного города до другого, граф Гамильтон приписывает некоторое число (зрелищность), которое является степенью числа 2. Поскольку по разные стороны от одной дороги пейзажи различны, то зрелищность дороги при проезде по ней в одну сторону отличается от зрелищности при проезде в другую сторону. Более того, оказалось, что все дороги имеют различную зрелищность. Граф хочет выбрать замкнутый маршрут (начинающийся и заканчивающийся в одном и том же городе), проходящий через все города по одному разу и имеющий максимальную суммарную зрелищность.
Напишите программу, которая определит оптимальный замкнутый маршрут для графа Гамильтона.
В первой строке задается целое число N - количество городов (2 ≤ N ≤ 1000). В каждой из последующих N строк задается по N чисел. Если j-ое число в i-ой строке равно c_ij, то зрелищность дороги из города i в город j равна 2^cij. Все числа c_ij различны и находятся в диапазоне от 0 до 10^6 включительно. Значения c_ii всегда задаются равными -1, что означает, что дороги из города i в него же, не проходящей через какой-либо другой город, не существует.
Выведите номера всех городов в той последовательности, в которой графу Гамильтону следует их посетить, чтобы его маршрут имел наибольшую зрелищность. Каждый город в этой последовательности должен встречаться ровно один раз, кроме одного - города, из которого граф начнет свой маршрут. Этот город должен встретиться дважды - в начале и в конце маршрута. В случае, если существует несколько оптимальных маршрутов, можно вывести любой из них.