This page is still under construction.

Parts of this page are still being built. What you see may change.

A Treasure Or A Bomb

Time limit8sMemory limit512 MB

Summary
Assign each key to a distinct keyhole to maximize the product of (1 - p_ij), printing the chosen key per keyhole; N up to 100, multiple test cases.
Level

Hard8 of 10

Topics
Dynamic programming, Math, Matrix, Implementation
Solved
No attempts yet

Problem

An adventurer seeking a legendary treasure discovered a mysterious door in a deep cavern. The door had many keyholes, and the same number of keys lay beside it. The keyholes were numbered from 1 to N, and the keys were numbered the same way.

According to the treasure map he carried, the door would open and lead him to the treasure room if he inserted all the keys into the keyholes at the same time. A key could go into any keyhole, so the task looked easy, but the door held one big trap. Whenever a key was inserted into a keyhole, a bomb planted in the door could explode with some probability.

The kindly treasure map listed every pijp_{ij}, the probability of explosion when the i-th keyhole was plugged by the j-th key. The cautious but greedy adventurer decided to insert the keys so as to maximize safety, that is, to maximize the probability of no explosion. Suppose there are two keys and two keyholes with p11=0.4p_{11} = 0.4, p12=0.5p_{12} = 0.5, p21=0.5p_{21} = 0.5, p22=0.6p_{22} = 0.6. If he inserts the first key into the first keyhole and the second into the second, the probability of no explosion is (1−0.4)×(1−0.6)=0.24(1 - 0.4) \times (1 - 0.6) = 0.24. If instead he inserts the second key into the first hole and the first key into the second, the probability is 0.25, which is better.

You are to find the best way to insert the keys. You may assume the answer is unique. The maximum probability of no explosion is strictly more than 1.00001 times the probability of any non-optimal insertion.

Input

The input consists of multiple test cases. Each test case begins with a line containing a single integer N (1 ≤ N ≤ 100), the number of keys and keyholes. In the following N lines, the i-th line contains N real numbers pi1,…,piNp_{i1}, \ldots, p_{iN} (0.00001 ≤ pijp_{ij} ≤ 0.99999). pijp_{ij} gives the probability of explosion when the i-th keyhole is plugged by the j-th key. Real numbers are given in decimal form with at most five digits after the decimal point.

The input is terminated by a line containing a single zero.

Output

For each test case, output N lines. The i-th line for a test case should contain only one integer, the key the adventurer should insert into the i-th keyhole. Separate the outputs for different test cases with one blank line.

Examples1

  1. Example 1

    Input
    3
0.8 0.9 0.1
0.1 0.4 0.5
0.6 0.1 0.7
2
0.4 0.5
0.5 0.6
0
    Expected output
    3
1
2

2
1