Getting Confidence

Interview

Time limit0.5sMemory limit512 MB

Summary

Given an N by N matrix of confidence values, assign each of N ornaments to a distinct position so that the product of the chosen values is maximized, and output the assignment.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Matrix, Combinatorics
Solved: No attempts yet

Problem

Sicrana loves ornaments. At home, she has N ornaments displayed in a row on a large shelf. Each ornament is identified by a distinct integer between 1 and N.

One day, while playing ball indoors, Sicrana's son Fulano hit his mother's ornament shelf with the ball, knocking all the ornaments to the floor. Luckily, no ornament was damaged by the fall. If Fulano puts all the ornaments back on the shelf exactly as they once were, his mother may not realize that anything wrong has happened.

Fulano has a bad memory, so he cannot remember the original order of the ornaments and needs your help. For each ornament i, Fulano will tell you N numbers between 1 and 100, where the j-th value is how confident Fulano is that ornament i was originally in position j on the shelf. To maximize Fulano's confidence that he will not get grounded, when choosing an order and placing the ornaments, Fulano multiplies the confidence that each ornament is in the right place. More formally, Fulano's total confidence for a given order of the ornaments is computed as follows. If pi is the position occupied by the i-th ornament and a(i, j) is Fulano's confidence that ornament i was originally in position j, then Fulano's total confidence is given by ∏a(i, pi).

Since there are so many ways to position the ornaments, your mission, if you accept it, is to find the order that maximizes Fulano's total confidence.

Input

The first line of input contains an integer N (1 ≤ N ≤ 100), the number of ornaments. Each of the following N lines contains N integers between 1 and 100. The j-th value in the i-th line is how confident Fulano is that ornament i was originally in position j on the shelf.

Output

Your program must output a single line containing N integers, the order in which Fulano should place the ornaments to maximize his total confidence. If more than one order gives the maximum confidence, any of them is accepted.

Examples2

Example 1
Input
```
3
1 15 37
42 8 25
77 2 1
```
Expected output
```
3 1 2
```
Example 2
Input
```
2
15 1
33 42
```
Expected output
```
1 2
```