Problem: Information technologies are developing and are increasingly penetrating into all spheres of human activity. Incredible as it is, the most modern technology are used in farming!

A large farm has a meadow with grazing sheep. Overall there are n sheep and each of them contains a unique number from 1 to n — because the sheep need to be distinguished and you need to remember information about each one, and they are so much alike! The meadow consists of infinite number of regions numbered from 1 to infinity. It's known that sheep i likes regions from li to ri.

There are two shepherds taking care of the sheep: First and Second. First wakes up early in the morning and leads the sheep graze on the lawn. Second comes in the evening and collects all the sheep.

One morning, First woke up a little later than usual, and had no time to lead the sheep graze on the lawn. So he tied together every two sheep if there is a region they both like. First thought that it would be better — Second would have less work in the evening, because sheep won't scatter too much, being tied to each other!

In the evening Second came on the lawn, gathered the sheep and tried to line them up in a row. But try as he might, the sheep wouldn't line up as Second want! Second had neither the strength nor the ability to untie the sheep so he left them as they are, but with one condition: he wanted to line up the sheep so that the maximum distance between two tied sheep was as small as possible. The distance between the sheep is the number of sheep in the ranks that are between these two.

Help Second find the right arrangement.

Input

The first input line contains one integer n (1 ≤ n ≤ 2000). Each of the following n lines contains two integers li and ri (1 ≤ li, ri ≤ 109; li ≤ ri).

Output

In the single output line print n space-separated numbers — the sought arrangement of the sheep. The i-th value in the line must represent the number of the sheep that took the i-th place from left in the optimal arrangement line. 

If there are multiple optimal arrangements, print any of them.

Examples

Input

3
1 3
5 7
2 4


Output

1 3 2

Input

5
1 5
2 4
3 6
1 7
2 6


Output

2 1 3 5 4

Input

4
1 3
4 6
5 7
2 3


Output

1 4 2 3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
pair<int, int> operator-(const pair<int, int> &a, const pair<int, int> &b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
pair<int, int> &operator+=(pair<int, int> &a, const pair<int, int> &b) {
  a.first += b.first;
  a.second += b.second;
  return a;
}
pair<int, int> &operator-=(pair<int, int> &a, const pair<int, int> &b) {
  a.first -= b.first;
  a.second -= b.second;
  return a;
}
template <class T, class U>
bool cmp_second(const pair<T, U> &a, const pair<T, U> &b) {
  return a.second < b.second;
}
template <class T>
T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  while (b) {
    T t = b;
    b = a % b;
    a = t;
  }
  return a;
}
template <class T>
pair<T, T> ext_gcd(T a, T b) {
  T a0 = 1, a1 = 0, b0 = 0, b1 = 1;
  if (a < 0) {
    a = -a;
    a0 = -1;
  }
  if (b < 0) {
    b = -b;
    b1 = -1;
  }
  while (b) {
    T t, q = a / b;
    t = b;
    b = a - b * q;
    a = t;
    t = b0;
    b0 = a0 - b0 * q;
    a0 = t;
    t = b1;
    b1 = a1 - b1 * q;
    a1 = t;
  }
  return make_pair(a0, a1);
}
inline int sg(int x) { return x ? (x > 0 ? 1 : -1) : 0; }
const int inf = 1000000;
class Segment {
 public:
  int l, r, id;
};
class Node {
 public:
  int vl, vr;
  int cnt, mii;
  pair<int, int> mil;
  priority_queue<int, vector<int>, greater<int> > pq;
  Node *_l, *_r;
  Node(int vl, int vr) : vl(vl), vr(vr) {
    cnt = 0;
    mil = make_pair(inf, -1);
    mii = inf;
    if (vl == vr) pq.push(inf);
    _l = _r = NULL;
  }
  ~Node() {
    delete _l;
    delete _r;
  }
  Node *left() {
    if (!_l) _l = new Node(vl, (vl + vr) / 2);
    return _l;
  }
  Node *right() {
    if (!_r) _r = new Node((vl + vr) / 2 + 1, vr);
    return _r;
  }
  void insert(int x, int ind) {
    cnt++;
    mii = min(mii, ind);
    if (vl == vr) {
      if (cnt)
        mil = make_pair(vl - cnt, vl);
      else
        mil = make_pair(inf, -1);
      pq.push(ind);
    } else {
      int m = (vl + vr) / 2;
      if (x <= m)
        left()->insert(x, ind);
      else
        right()->insert(x, ind);
      mil = min(left()->mil, right()->mil - make_pair(left()->cnt, 0));
    }
  }
  int getmin(int r) {
    if (r == vr)
      return mii;
    else {
      int m = (vl + vr) / 2;
      if (r <= m)
        return left()->getmin(r);
      else
        return min(left()->getmin(m), right()->getmin(r));
    }
  }
  int takemin(int r) { return takemin(r, getmin(r)); }
  int takemin(int r, int minval) {
    cnt--;
    if (vl == vr) {
      int ind = pq.top();
      pq.pop();
      mii = pq.top();
      if (cnt)
        mil = make_pair(vl - cnt, vl);
      else
        mil = make_pair(inf, -1);
      return ind;
    } else {
      int ret, m = (vl + vr) / 2;
      if (r <= m)
        ret = left()->takemin(r, minval);
      else if (left()->mii == minval)
        ret = left()->takemin(m, minval);
      else
        ret = right()->takemin(r, minval);
      mii = min(left()->mii, right()->mii);
      mil = min(left()->mil, right()->mil - make_pair(left()->cnt, 0));
      return ret;
    }
  }
};
int n;
Segment segbyr[2050], segbyl[2050];
int ans[2050], id2ri[2050];
bool used[2050];
bool cmpr(const Segment &a, const Segment &b) {
  if (a.r != b.r)
    return a.r < b.r;
  else
    return a.l < b.l;
}
bool cmpl(const Segment &a, const Segment &b) { return a.l < b.l; }
bool valid(int thr) {
  int sbli = 0, sbri = 0;
  Node tr(0, n);
  for (int i = 0; i < n; i++) used[i] = 0;
  for (int i = 0; i < n; i++) {
    int lb = tr.mil.first;
    int at = tr.mil.second;
    int ind;
    if (lb < i) return 0;
    if (lb > i) {
      while (sbri < n && used[sbri]) sbri++;
      assert(sbri < n);
      if (tr.getmin(n) == sbri)
        ind = tr.takemin(n);
      else
        ind = sbri;
    } else {
      ind = tr.takemin(at);
    }
    ans[i] = segbyr[ind].id;
    used[ind] = 1;
    while (sbli < n && segbyl[sbli].l <= segbyr[ind].r) {
      int u = id2ri[segbyl[sbli++].id];
      if (used[u]) continue;
      tr.insert(i + thr, u);
    }
  }
  return 1;
}
void solve() {
  sort(segbyr, segbyr + n, cmpr);
  sort(segbyl, segbyl + n, cmpl);
  for (int i = 0; i < n; i++) id2ri[segbyr[i].id] = i;
  int lb = -1, rb = n;
  while (lb < rb - 1) {
    int m = (lb + rb) / 2;
    if (valid(m))
      rb = m;
    else
      lb = m;
  }
  valid(rb);
  for (int i = 0; i < n; i++)
    printf("%d%c", ans[i] + 1, i + 1 < n ? ' ' : '\n');
}
int main(void) {
  vector<pair<int, int> > e;
  scanf("%d", &(n));
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &(segbyr[i].l), &(segbyr[i].r));
    segbyr[i].id = i;
    segbyl[i] = segbyr[i];
  }
  solve();
  return 0;
}