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 ulaznog fajla loto.in 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 izlaznog fajla loto.out 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

const
  fin = 'loto.in';
  fout = 'loto.out';
  MaxN = 3000;

type
  TVector = record
    x, y : Longint;
    id : Integer;
  end;

var
  n : Integer;
  p : array[0..MaxN] of TVector;
  min : array[1..MaxN] of Integer;



   function Compare(const a, b : TVector) : Longint;
   begin
     if a.x <> b.x then
       Compare := a.x - b.x
     else
       Compare := a.y - b.y;
   end;


   function Prod(const a, b : TVector) : Shortint;
   var
      p : Longint;
   begin
     p := a.x*b.y - a.y*b.x;

      if p < 0 then
         Prod := -1
      else
         if p > 0 then
            Prod := 1
         else
            if (a.x*b.x > 0) or (a.y*b.y > 0) then
               Prod := 0
            else
               Prod := 2;
   end;


   function Sub(const a, b : TVector) : TVector;
   var
     c : TVector;
   begin
     c.x := a.x - b.x;
     c.y := a.y - b.y;
     Sub := c;
   end;


   function Perp(const a : TVector) : TVector;
   var
     c : TVector;
   begin
     c.x := -a.y;
     c.y := a.x;
     Perp := c;
   end;



   var
      m, t : TVector;

   procedure Sort(l, r : Integer);
   var
     i, j : Integer;
   begin
     i := l;
     j := r;
     m := p[(l + r) div 2];
     repeat
       while Compare(p[i], m) < 0 do Inc(i);
       while Compare(p[j], m) > 0 do Dec(j);
       if i <= j then
       begin
         t := p[i];
         p[i] := p[j];
         p[j] := t;
         inc(i);
         dec(j);
       end;
     until i > j;

     if l < j then Sort(l, j);
     if i < r then Sort(i, r);
   end;


  procedure Solve;
  var
    k, i, j : Integer;
    m, mc : Integer;
    c : array[0..MaxN+1] of Integer;
    cn, d : Integer;
      boundL, boundH : TVector;
    t1, t2 : TVector;
      valid : Boolean;
  begin
    Sort(1, n);

    for k := n downto 2 do
    begin
         // nalazenje konveksnog omotaca (tacke su vec sortirane)
      cn := 1;
      c[1] := 1;
      d := 1;
      for i := 2 to 2*k-1 do
      begin
        j := k - Abs(k - i);
        while (cn > d) and (Prod(Sub(p[c[cn]], p[c[cn-1]]), Sub(p[j], p[c[cn]])) <= 0) do
          Dec(cn);
        Inc(cn);
        c[cn] := j;
        if i = k then d := cn;
      end;
      dec(cn);
         c[0] := c[cn];


      // nalazenje dozvoljene tacke na konveksnom omotacu sa najmanjom oznakom
         m := 0;
      p[0].id := n + 1;
      for i := 1 to cn do
      begin
            if (k = n) then
               valid := true
            else
            begin
               t1 := Perp(Sub(p[c[i]], p[c[i-1]]));
             t2 := Perp(Sub(p[c[i+1]], p[c[i]]));

               if Prod(boundL, t1) < 0 then
                  valid := Prod(boundL, t2) = 1
               else
                  valid := Prod(t1, boundH) > 0;
            end;

            if valid and (p[c[i]].id < p[m].id) then
        begin
          m := c[i];
          mc := i;
        end;
         end;

         min[n-k+1] := p[m].id;


         // suzavamo dozvoljeni interval pravaca
         t1 := Perp(Sub(p[c[mc]], p[c[mc-1]]));
      t2 := Perp(Sub(p[c[mc+1]], p[c[mc]]));

         if (k = n) or (Prod(t2, boundH) > 0) then boundH := t2;
      if (k = n) or (Prod(t1, boundL) < 0) then boundL := t1;


      // izbacivanje tacke m iz daljeg razmatranja (tacke ostaju sortirane)
         for i := m to k-1 do
            p[i] := p[i+1];
      end;
      min[n] := p[1].id;
  end;


  procedure ReadInput;
  var
    f : Text;
    i : Integer;
  begin
    Assign(f, fin);
    Reset(f);
    Readln(f, n);
    for i := 1 to n do
    begin
      Readln(f, p[i].x, p[i].y);
      p[i].id := i - 1;
    end;
    Close(f);
  end;


  procedure WriteOutput;
  var
    f : Text;
    i : Integer;
  begin
    Assign(f, fout);
    Rewrite(f);
    for i := 1 to n do
      Writeln(f, min[i]);
    Close(f);
  end;



begin
  ReadInput;
  Solve;
  WriteOutput;
end.