#include <bits/stdc++.h>
using namespace std;
enum STATE { IN, OUT, BOUNDRY };
void fast_in_out() {
  std::ios_base::sync_with_stdio(NULL);
  cin.tie(NULL);
  cout.tie(NULL);
}
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
int dy[] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
int lx[] = {2, 2, -1, 1, -2, -2, -1, 1};
int ly[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const long double eps = 1e-3;
const int N = 1e6 + 100, M = 5e2 + 50, mod = 1e9 + 7;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int main() {
  fast_in_out();
  int n;
  cin >> n;
  vector<pair<pair<int, int>, int>> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].first.second;
    cin >> v[i].first.first;
    v[i].second = i;
  }
  vector<int> ans(n);
  sort(v.begin(), v.end());
  map<int, bool> mp;
  for (int i = 0; i < n; i++) {
    int s = v[i].first.second;
    int e = v[i].first.first;
    while (mp.count(s)) s++;
    mp[s] = 1;
    ans[v[i].second] = s;
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
enum STATE { IN, OUT, BOUNDRY };
void fast_in_out() {
  std::ios_base::sync_with_stdio(NULL);
  cin.tie(NULL);
  cout.tie(NULL);
}
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
int dy[] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
int lx[] = {2, 2, -1, 1, -2, -2, -1, 1};
int ly[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const long double eps = 1e-3;
const int N = 1e6 + 100, M = 5e2 + 50, mod = 1e9 + 7;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int main() {
  fast_in_out();
  int n;
  cin >> n;
  vector<pair<pair<int, int>, int>> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].first.second;
    cin >> v[i].first.first;
    v[i].second = i;
  }
  vector<int> ans(n);
  sort(v.begin(), v.end());
  map<int, bool> mp;
  for (int i = 0; i < n; i++) {
    int s = v[i].first.second;
    int e = v[i].first.first;
    while (mp.count(s)) s++;
    mp[s] = 1;
    ans[v[i].second] = s;
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  return 0;
}

```