Скарб чи бомба
Авантюрист, шукаючи легендарний скарб, натрапив на таємничі двері в глибині печери. Двері мали багато замкових щілин, і поруч з ними лежала така ж кількість ключів. Замкові щілини були пронумеровані від 1 до N, так само як і ключі.
Згідно з картою скарбів, яку він мав, двері відчиняться і приведуть його до кімнати зі скарбами, якщо він вставить усі ключі в замкові щілини одночасно. Кожен ключ може бути вставлений у будь-яку замкову щілину, тому це здавалося легким завданням — але насправді це було не так, тому що на дверях була одна велика пастка. Коли кожен з ключів був вставлений у замкову щілину, бомба, закладена в дверях, могла вибухнути з певною ймовірністю.
На доброзичливій карті скарбів були вказані всі p_ij (ймовірність вибуху, коли i^{-та} замкова щілина була закрита j^{-тим} ключем). Обережний, але жадібний авантюрист вирішив вставити ключі так, щоб максимізувати безпеку, тобто максимізувати ймовірність не вибуху. Припустимо ситуацію з двома ключами та замковими щілинами, де p_{11 }= 0.4, p_{12 }= 0.5, p_21 = 0.5, p_22 = 0.6. Якщо він вставить перший ключ у першу замкову щілину, а другий у другу, ймовірність не вибуху становить (1-0.4)×(1-0.6) = 0.24. З іншого боку, якщо він вставить другий ключ у першу щілину, а перший ключ у другу, тоді ймовірність становить 0.25, що краще.
Вам потрібно знайти найкращий спосіб вставити ключі. Ви можете припустити, що відповідь є унікальною. Максимальна ймовірність не вибуху є строго 1.00001 рази більшою, ніж ймовірність з будь-яким неоптимальним вставленням ключів.
Вхідні дані
Вхід для цієї задачі складається з кількох тестових випадків. Кожен випадок починається з рядка, що містить одне ціле число N (1 ≤ N ≤ 100), яке вказує кількість ключів і замкових щілин.
У наступних N рядках, i^{-й} рядок містить N дійсних чисел p_i1, ..., p_iN (0.00001 ≤ p_ij ≤ 0.99999). p_ij дає ймовірність вибуху, коли i^{-та} замкова щілина закрита j^{-тим} ключем. Дійсні числа представлені у десятковій формі з не більше ніж п'ятьма знаками після коми.
Вхід завершується рядком, що містить один нуль.
Вихідні дані
Для кожного тестового випадку виведіть N рядків. i^{-й} рядок для кожного тестового випадку повинен містити лише одне ціле число, яке представляє ключ, який авантюрист повинен вставити в i^{-ту} замкову щілину. Виходи для різних тестових випадків повинні бути розділені одним порожнім рядком.