U zemlji Srećiji zavladala je nova pošast – nagradna igra na sreću Loto. Pravila ove igre su sledeća: iz bubnja koji sadrži n kuglica numerisanih brojevima od 0 do n-1 sve kuglice se izvlače nekim redosledom i pobednik je onaj koji pogodi tačan redosled kuglica. Bubanj je oblika horizontalno postavljene kružne ploče na kojoj se nalaze kuglice Iznos nagrade koja se dodeljuje pobedniku računa se kao zbir brojeva oblika a_i*10000^n-i, gde a_i označava broj kuglice koja je izašla i-ta po redu.

Prošlo je već mnogo vremena od kada je Loto startovao a još se nije pojavio nijedan srećni dobitnik, i to je nagnalo ljude da počnu da sumnjaju u verodostojnost igre. Međutim, dok se ostali samo žale kako je sve to namešteno, profesor Đurić, stari vuk igara na sreću, je izračunao da je iznos eventualnog dobitka veći nego što bi ga koštala uplata svih mogućih kombinacija, pa je odlučio da na taj način zaradi. Nestrpljivo iščekujući dan kada će konačno biti dodeljena premija, možete zamisliti naše zaprepašćenje kada su u naše prostorije banuli predstavnici organizatora ove igre i rekli nam da je sve zaista namešteno (1:0 za narod), i da nas mole, pošto na sledećem izvlačenju svakako moraju da dodele premiju (1:0 za profesora Đurića), da im pomognemo da iznos nagrade bude što manji.

Loto se namešta na sledeći način: ispod bubnja, paralelno sa njegovom ravni, nalazi se jak magnet u obliku šipke, koji se može postaviti u proizvoljan položaj. U tačno određenom momentu magnet se aktivira što uzrokuje da se sve kuglice momentalno prilepe za njega (kuglica na magnet doleće pod pravim uglom) i u tom redosledu izađu iz bubnja.

Naše zaprepašćenje još uvek traje, a pošto nismo sigurni ni koliko je sve to moralno, odlučili smo da problem predamo vama – odredite kombinaciju koja će organizatore koštati što manje.

Ulaz:

U prvoj liniji standardnog ulaza se nalazi prirodan broj n (1 ≤ n ≤ 3000), broj kuglica. U narednih n linija se nalaze celi brojevi x_i, y_i razdvojeni prazninom (-15000 ≤ x_i, y_i ≤ 15000), koordinate kuglice i u momentu uključivanja magneta. Kuglice su opisane redom, počev od kuglice sa oznakom 0, do kuglice sa oznakom n-1.

Izlaz:

U n linija standardnog izlaza upisati brojeve kuglica u redosledu u kom izlaze pri najpovoljnijem položaju magneta, tako da se u i-tom redu nalazi broj kuglice koja izlazi i-ta po redu.

Primer:

5
1 3
0 4
4 4
0 0
4 0

1
0
2
3
4

Objašnjenje

Minimalnu vrednost glavnog dobitka postići ćemo ako magnet postavimo kao na slici. Glavni dobitak u tom slučaju iznosi: 1∙10000⁴ + 0∙10000³ + 2∙10000² + 3∙10000 + 4