Dance Partner Pairing

A school is organizing a freshman dance party where n boys and n girls will be paired to dance together. For every boy i and girl j, you are given two scores:

• A_i,j: the familiarity (or joy) score between boy i and girl j
• B_i,j: the disharmony (or inconvenience) score when they dance together. You may assume every element in matrix B is positive.

The pairing produces n pairs. Let the joy scores of the pairs be a'1, a'2, ..., a'n and the disharmony scores be b'1, b'2, ..., b'n. We define the overall quality of a pairing as:

\( C = \frac{a'_1+a'_2+\cdots+a'_n}{b'_1+b'_2+\cdots+b'_n} \)

Cathy, the experienced senior, wants a pairing that maximizes the value of \( C \). Your task is to help her by writing a program to compute a perfect matching (a one-to-one pairing between boys and girls) which maximizes \( C \). If there are multiple optimal solutions, any one is acceptable.

In the output, for each boy (in order from 1 to n) print the index (1-indexed) of the girl he is paired with.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 100) representing the number of boys and girls. This is followed by n lines, each containing n integers, representing the matrix A (the familiarity scores). Then, there are n lines, each containing n integers, representing the matrix B (the disharmony scores). All entries in matrix B are positive.

outputFormat

Output a single line containing n integers. The i-th integer indicates the index (1-indexed) of the girl paired with the i-th boy. Any optimal pairing that maximizes
\( C = \frac{\sum_{i=1}^{n}a'_i}{\sum_{i=1}^{n}b'_i} \) is acceptable.

sample

2
10 1
1 10
1 2
2 1

1 2