Almost Assignment - Weekly Challenge 1: Approximation | Repovive

W1D3A. Almost Assignment

1 pts1s256 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$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

W1D3A. Almost Assignment

Constraints

Input

Output

Samples

W1D3A. Almost Assignment

Constraints

Input

Output

Samples