Сокровище или бомба
Авантюрист, в поисках легендарного сокровища, наткнулся на загадочную дверь в глубокой пещере. Дверь имела множество замочных скважин, и рядом с ней находилось такое же количество ключей. Замочные скважины были пронумерованы от 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-ю замочную скважину. Выводы для разных тестов должны быть разделены одной пустой строкой.