Almost Assignment - Testing Approx Problems | Repovive

1012E. Almost Assignment

1s256 MB

You are given $n$ workers and $n$ jobs.

If worker $i$ is assigned to job $j$ , you gain profit $a_{i,j}$ .

You must assign each worker to exactly one job, and each job to exactly one worker. In other words, you must choose a permutation $p_1,p_2,\ldots,p_n$ , where worker $i$ is assigned to job $p_i$ .

The score of an assignment is:

$\sum_{i=1}^{n} a_{i,p_i}$

Let $OPT$ be the maximum possible score of an assignment.

You do not need to find an optimal assignment. You only need to output any assignment whose score is at least half of $OPT$ .

In other words, if the score of your assignment is $S$ , your output is accepted if $2 \times S \ge OPT$ .

Constraints

$1 \le t \le 3$
$1 \le n \le 900$
The sum of $n^2$ over all test cases is at most $900000$
$1 \le a_{i,j} \le 10^9$

Input

The input is given in the following format:

t

\left. \begin{array}{l} n \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,n} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,n} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,n} \end{array} \right\} \times t

Output

For each test case, output a permutation $p_1,p_2,\ldots,p_n$ .

This means each integer from $1$ to $n$ must appear exactly once. Worker $i$ will be assigned to job $p_i$ .

If the score of your assignment is $S$ , it must satisfy $2 \times S \ge OPT$ .

The output format is:

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Samples

Input

Explanation

The shown assignment gives jobs $1,2,3,4,5$ to workers $1,2,3,4,5$ respectively.

Its score is $10+1+20+18+16=65$ .

This is not optimal: assigning jobs $2,1,3,4,5$ gives score $8+9+20+18+16=71$ . Still, the shown assignment is accepted because $2 \times 65 \ge 71$ .

Output

1 2 3 4 5

You are given $n$ workers and $n$ jobs.

If worker $i$ is assigned to job $j$ , you gain profit $a_{i,j}$ .

You must assign each worker to exactly one job, and each job to exactly one worker. In other words, you must choose a permutation $p_1,p_2,\ldots,p_n$ , where worker $i$ is assigned to job $p_i$ .

The score of an assignment is:

$\sum_{i=1}^{n} a_{i,p_i}$

Let $OPT$ be the maximum possible score of an assignment.

You do not need to find an optimal assignment. You only need to output any assignment whose score is at least half of $OPT$ .

In other words, if the score of your assignment is $S$ , your output is accepted if $2 \times S \ge OPT$ .

$1 \le t \le 3$
$1 \le n \le 900$
The sum of $n^2$ over all test cases is at most $900000$
$1 \le a_{i,j} \le 10^9$

The input is given in the following format:

t

\left. \begin{array}{l} n \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,n} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,n} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,n} \end{array} \right\} \times t

For each test case, output a permutation $p_1,p_2,\ldots,p_n$ .

This means each integer from $1$ to $n$ must appear exactly once. Worker $i$ will be assigned to job $p_i$ .

If the score of your assignment is $S$ , it must satisfy $2 \times S \ge OPT$ .

The output format is:

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

The shown assignment gives jobs $1,2,3,4,5$ to workers $1,2,3,4,5$ respectively.

Its score is $10+1+20+18+16=65$ .

This is not optimal: assigning jobs $2,1,3,4,5$ gives score $8+9+20+18+16=71$ . Still, the shown assignment is accepted because $2 \times 65 \ge 71$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1012E. Almost Assignment

Constraints

Input

Output

Samples

1012E. Almost Assignment

Constraints

Input

Output

Samples