Problem: On a history lesson the teacher asked Vasya to name the dates when n famous events took place. He doesn't remembers the exact dates but he remembers a segment of days [li, ri] (inclusive) on which the event could have taken place. However Vasya also remembers that there was at most one event in one day. Help him choose such n dates of famous events that will fulfill both conditions. It is guaranteed that it is possible.

Input

The first line contains one integer n (1 ≤ n ≤ 100) — the number of known events. Then follow n lines containing two integers li and ri each (1 ≤ li ≤ ri ≤ 107) — the earliest acceptable date and the latest acceptable date of the i-th event.

Output

Print n numbers — the dates on which the events took place. If there are several solutions, print any of them. It is guaranteed that a solution exists.

Examples

Input

3
1 2
2 3
3 4


Output

1 2 3 


Input

2
1 3
1 3


Output

1 2 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int inf = 0x3f3f3f3f;
struct node {
  int id, val, f;
} e[N << 1];
struct node2 {
  int l, r, id;
} w[N];
struct node3 {
  int l, r, MIN;
} tr[N * N * 10];
int n, MIN = inf, fid[N * 2 * N];
bool cmp(const node &a, const node &b) { return a.val < b.val; }
bool cmp2(const node2 &a, const node2 &b) {
  if (a.r != b.r) return a.r < b.r;
  return a.l < b.l;
}
void up(int x) { tr[x].MIN = min(tr[x << 1].MIN, tr[x << 1 | 1].MIN); }
void build(int L, int R, int x) {
  tr[x].l = L;
  tr[x].r = R;
  if (L == R) {
    tr[x].MIN = L;
    return;
  }
  int mid = L + R >> 1;
  build(L, mid, x << 1);
  build(mid + 1, R, x << 1 | 1);
  up(x);
}
void update(int id, int x) {
  if (tr[x].l == tr[x].r) {
    tr[x].MIN = inf;
    return;
  }
  int mid = tr[x].l + tr[x].r >> 1;
  if (mid >= id)
    update(id, x << 1);
  else
    update(id, x << 1 | 1);
  up(x);
}
int find(int L, int R, int x) {
  if (tr[x].l >= L && tr[x].r <= R) return tr[x].MIN;
  int mid = tr[x].l + tr[x].r >> 1;
  if (mid >= R)
    return find(L, R, x << 1);
  else if (mid < L)
    return find(L, R, x << 1 | 1);
  else
    return min(find(L, mid, x << 1), find(mid + 1, R, x << 1 | 1));
}
void init() {
  for (int i = 0; i < 2 * n; ++i) e[i].val -= MIN - 1;
  sort(e, e + 2 * n, cmp);
  int t = 1;
  for (int i = 0; i < 2 * n; ++i) {
    int id = e[i].id, d;
    if (i == 0 || e[i].val == e[i - 1].val) {
      fid[t] = e[i].val;
      d = 0;
    } else if (e[i].val - e[i - 1].val <= n) {
      d = e[i].val - e[i - 1].val;
      for (int j = t; j <= t + d; ++j) fid[j] = e[i - 1].val + j - t + MIN - 1;
    } else {
      for (int j = t; j <= t + n; ++j) fid[j] = e[i - 1].val + j - t + MIN - 1;
      d = n;
    }
    t += d;
    if (e[i].f)
      w[id].r = t;
    else
      w[id].l = t;
  }
  build(1, t, 1);
}
int res[N];
void gao() {
  sort(w, w + n, cmp2);
  for (int i = 0; i < n; ++i) {
    int s = w[i].l, t = w[i].r;
    int g = find(s, t, 1);
    update(g, 1);
    res[w[i].id] = fid[g];
  }
  for (int i = 0; i < n; ++i) printf("%d ", res[i]);
  puts("");
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &e[i].val, &e[i + n].val);
    MIN = min(e[i].val, MIN);
    e[i].id = e[i + n].id = i;
    e[i].f = 0, e[i + n].f = 1;
    w[i].id = i;
  }
  init();
  gao();
  return 0;
}