In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

We are given independent and indivisible jobs numbered from to . They should be executed sequentially in any order. The later the execution of a job starts the longer it lasts - precisely, the time of execution of the job is , if we start it in the moment . We assume that , .

The goal is to schedule the jobs so that the total execution time is the shortest.

Write a program that:

- reads from the standard input the number of jobs not greater than and successively - for each job - the coefficients and determining the dependence of the job execution time upon the time it starts,
- finds such a scheduling of the jobs that the cumulative execution time is minimal; then the program writes to the standard output the numbers of the jobs in the order they should be executed.

- In the first line of the standard input there is one positive integer not greater then . It is the number of jobs .
- In each of the following lines there is a pair of nonnegative real numbers. The numbers are written in a standard form with a decimal point and six digits after the point. The numbers are separated by a single space. It is the pair of coefficients and determining the dependence of the execution time of the corresponding -th job upon the time it starts.

One should write in the standard output the scheduling of the jobs, i.e. an appropriate permutation of numbers ; one number per line.

For the input data:

5 0.002000 0.003000 0.016000 0.001000 0.100000 0.300000 0.016000 0.005000 0.030000 0.060000

the correct result is:

2 4 1 5 3

*Task author: Marcin Jurdzinski.*