Одного разу граф Уільям Гамільтон вирішив здійснити кругосвітну подорож, у якій він відвідав би 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 у нього ж, яка не проходить через якесь інше місто, не існує.
Виведіть номери всіх міст у тій послідовності, у якій графу Гамільтону слід їх відвідати, щоб його маршрут мав найбільшу видовищність. Кожне місто у цій послідовності повинно зустрітись рівно один раз, окріме одного - міста, з якого граф почне свій маршрут. Це місто повинно зустрітись двічі - на початку і в кінці маршруту. У випадку, якщо існує декілька оптимальних маршрутів, можна вивести довільний з них.