Ko je ona tvrda glava, što do podne uvek spava? Ko je dasa u ekstazi, kada preko stotke gazi? Naravno, to je Flojd. Flojd je mudar, hrabar i ludo vozi. Međutim, čak i takvom reli asu je ponekad potrebna pomoć.

Organizatori predstojeće reli trke su odlučili da uvedu nova pravila. Na stazu su postavili N zastavica numerisanih brojevima od 1 do N, tako da i-ta zastavica ima koordinate (X_i, Y_i). Kao i svaki pravi reli, i ovaj naš se odvija na neuređenom, zemljanom terenu, na kome se tragovi točkova savršeno vide. Pravila trke su sledeća: vozač treba da izabere redosled zastavica z₁, ..., z_N, i potom pravolinijski ide od zastavice numerisane brojem z₁ do z₂, od z₂ do z₃, i tako sve dok ne stigne do zastavice z_N. Naravno, kako bi se umešnost vozača što više stavila na ispit, postoje i dodatna pravila koja donose dodatne poene. Naime, iz početne zastavice vozač sme da ide samo severno, odnosno ka zastavici koja ima veću y koordinatu. Potom sme da ide samo južno, odnosno ka zastavici koja ima manju y koordinatu, i tako dalje. Drugim reqima, treba da važi y_z1 < y_z2 > y_z3 < y_z4 > .... Takođe, nije dozvoljeno da trag koji točkovi ostavljaju ima samopresecanja, osim u tačkama na kojima se nalaze zastavice, i naravno, potrebno je obići svaku zastavicu tačno jednom. Pomozite Flojdu da nađe takvu putanju i time osvoji sve moguće poene i srca publike!

Ulaz.

(Ulazni podaci se učitavaju iz datoteke flojd.in.) U ulaznoj datoteci se u prvom redu nalazi broj N (1 ≤ N ≤ 5000), broj zastavica. U sledećih N redova se nalaze po dva cela broja iz intervala [1, 10⁷], pri čemu i-ti red sadrži (x_i, y_i), koordinate i-te zastavice. Nikoje tri tačke nisu kolinearne i ne postoje dve tačke sa istom y koordinatom.

Izlaz.

(Izlazni podaci se ispisuju u datoteku flojd.out) Ukoliko postoji putanja koja zadovoljava kriterijume, ispisati redne brojeve zastavice u redosledu u kojem ih treba obići, po jednu u svakom redu. Ukoliko postoji više mogućih putanja, štampati bilo koju. Ukoliko takva putanja ne postoji, ispisati -1.

Primer 1.

3
1 1
5 5
2 3

1
2
3

Napomena.
U 75% test primera ima najviše 3000 zastavica.

#include <iostream>
#include <cstdio>
using namespace std;

const char inFileName[] = "flojd.in";
const char outFileName[] = "flojd.out";

const int MaxN = 5001;

int n;
long x[MaxN], y[MaxN];

int next[MaxN], prev[MaxN];
bool used[MaxN];

bool right(int a, int b, int c) {
  long long A = y[b] - y[a], B = x[a] - x[b], C = A * x[a] + B * y[a];
  return A * x[c] + B * y[c] - C > 0;
}

int find_right(int a) {
  int r = -1;
 
  for (int i = 0; i < n; i++) {
    if (i == a || used[i]) continue;
    else {
      if (r == -1) r = i;
      else if (right(a, r, i)) r = i;
    }
  }
  return r;
}

int convex_hull() {
  long ysmall = y[0];
  int ind = 0;
  for (int i = 1; i < n; i++) {
    if (y[i] < ysmall) {
      ysmall = y[i];
      ind = i;
    }
  }

  int start = ind;
  next[ind] = ind;
  prev[ind] = ind;
  bool done = false;
  while (!done) {
    int nextInd = find_right(ind);
    prev[nextInd] = ind;
    next[ind] = nextInd;
    ind = nextInd;
    if (nextInd == start) 
      done = true;
  }

  return start;
}

void delete_point(int p) {
  int s = prev[p], q = next[p];
  while (s != q) {
    int nextS = find_right(s);
    next[s] = nextS;
    prev[nextS] = s;
    s = nextS;
  }
}

int main() {  
  freopen(inFileName, "r", stdin);
  freopen(outFileName, "w", stdout);
  
scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%ld %ld", &x[i], &y[i]);
    used[i] = false;
  }

  int currentPoint = convex_hull();
  bool pickHigher = true;
  for (int i = 0; i < n - 3; i++) {
    printf("%d\n", currentPoint+1);
    int c1 = prev[currentPoint], c2 = next[currentPoint];
    used[currentPoint] = true;
    delete_point(currentPoint);
    if (pickHigher) {
      if (y[c1] > y[c2]) currentPoint = c1;
      else currentPoint = c2;
    } else {
      if (y[c1] < y[c2]) currentPoint = c1;
      else currentPoint = c2;
    }
    pickHigher = !pickHigher;
  }

  int c1 = prev[currentPoint], c2 = next[currentPoint];
  if (pickHigher) {
    if (y[c1] < y[c2]) swap(c1, c2);
  } else {
    if (y[c1] > y[c2]) swap(c1, c2);
  }
  printf("%d\n%d\n%d\n", currentPoint+1, c1+1, c2+1);
  return 0;
}