#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
inline int two(int n) { return 1 << n; }
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    int g = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
  }
}
long long modpow(long long a, long long b) {
  long long res = 1;
  a %= 1000000007;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
  }
  return res;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
const int sz = 1e5 + 1, amt = 133;
bool w[sz], l[sz];
bool isWin[amt + 1];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ifstream in("input.txt");
  ofstream out("output.txt");
  int t;
  bool allwin, found, first;
  long long e, s, te, ts;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> s >> e;
    te = e;
    ts = s;
    found = false;
    allwin = false;
    while (te % 2 == 0 || allwin) {
      if (ts > te / 2) {
        if (allwin)
          w[i] = 1;
        else
          w[i] = (te - ts) & 1;
        found = true;
        break;
      }
      te >>= 1;
      allwin = !allwin;
    }
    if (!found) w[i] = (te - ts) & 1;
    te = e;
    ts = s;
    found = false;
    allwin = true;
    while (te % 2 == 0 || allwin) {
      if (ts > te / 2) {
        if (allwin)
          l[i] = 1;
        else
          l[i] = (te - ts) & 1;
        found = true;
        break;
      }
      te >>= 1;
      allwin = !allwin;
    }
    if (!found) l[i] = (te - ts) & 1;
  }
  bool wannawin = 1, wannalose = 1;
  for (int i = t - 1; i >= 1; i--) {
    if (wannawin) {
      if (w[i]) wannawin = 0;
    } else {
      if (!l[i]) wannawin = 1;
    }
    if (wannalose) {
      if (!l[i]) wannalose = 0;
    } else {
      if (w[i]) wannalose = 1;
    }
  }
  if (wannawin && w[0] || !wannawin && l[0])
    cout << 1 << " ";
  else
    cout << 0 << " ";
  if (wannalose && l[0] || !wannalose && w[0])
    cout << 1 << " ";
  else
    cout << 0 << " ";
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

Lee is used to finish his stories in a stylish way, this time he barely failed it, but Ice Bear came and helped him. Lee is so grateful for it, so he decided to show Ice Bear his new game called "Critic"...

The game is a one versus one game. It has t rounds, each round has two integers s_i and e_i (which are determined and are known before the game begins, s_i and e_i may differ from round to round). The integer s_i is written on the board at the beginning of the corresponding round. 

The players will take turns. Each player will erase the number on the board (let's say it was a) and will choose to write either 2 ⋅ a or a + 1 instead. Whoever writes a number strictly greater than e_i loses that round and the other one wins that round.

Now Lee wants to play "Critic" against Ice Bear, for each round he has chosen the round's s_i and e_i in advance. Lee will start the first round, the loser of each round will start the next round.

The winner of the last round is the winner of the game, and the loser of the last round is the loser of the game.

Determine if Lee can be the winner independent of Ice Bear's moves or not. Also, determine if Lee can be the loser independent of Ice Bear's moves or not.

Input

The first line contains the integer t (1 ≤ t ≤ 10^5) — the number of rounds the game has. 

Then t lines follow, each contains two integers s_i and e_i (1 ≤ s_i ≤ e_i ≤ 10^{18}) — the i-th round's information.

The rounds are played in the same order as given in input, s_i and e_i for all rounds are known to everyone before the game starts.

Output

Print two integers.

The first one should be 1 if Lee can be the winner independent of Ice Bear's moves, and 0 otherwise.

The second one should be 1 if Lee can be the loser independent of Ice Bear's moves, and 0 otherwise.

Examples

Input


3
5 8
1 4
3 10


Output


1 1


Input


4
1 2
2 3
3 4
4 5


Output


0 0


Input


1
1 1


Output


0 1


Input


2
1 9
4 5


Output


0 0


Input


2
1 2
2 8


Output


1 0


Input


6
216986951114298167 235031205335543871
148302405431848579 455670351549314242
506251128322958430 575521452907339082
1 768614336404564650
189336074809158272 622104412002885672
588320087414024192 662540324268197150


Output


1 0

Note

Remember, whoever writes an integer greater than e_i loses.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
inline int two(int n) { return 1 << n; }
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    int g = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
  }
}
long long modpow(long long a, long long b) {
  long long res = 1;
  a %= 1000000007;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
  }
  return res;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
const int sz = 1e5 + 1, amt = 133;
bool w[sz], l[sz];
bool isWin[amt + 1];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ifstream in("input.txt");
  ofstream out("output.txt");
  int t;
  bool allwin, found, first;
  long long e, s, te, ts;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> s >> e;
    te = e;
    ts = s;
    found = false;
    allwin = false;
    while (te % 2 == 0 || allwin) {
      if (ts > te / 2) {
        if (allwin)
          w[i] = 1;
        else
          w[i] = (te - ts) & 1;
        found = true;
        break;
      }
      te >>= 1;
      allwin = !allwin;
    }
    if (!found) w[i] = (te - ts) & 1;
    te = e;
    ts = s;
    found = false;
    allwin = true;
    while (te % 2 == 0 || allwin) {
      if (ts > te / 2) {
        if (allwin)
          l[i] = 1;
        else
          l[i] = (te - ts) & 1;
        found = true;
        break;
      }
      te >>= 1;
      allwin = !allwin;
    }
    if (!found) l[i] = (te - ts) & 1;
  }
  bool wannawin = 1, wannalose = 1;
  for (int i = t - 1; i >= 1; i--) {
    if (wannawin) {
      if (w[i]) wannawin = 0;
    } else {
      if (!l[i]) wannawin = 1;
    }
    if (wannalose) {
      if (!l[i]) wannalose = 0;
    } else {
      if (w[i]) wannalose = 1;
    }
  }
  if (wannawin && w[0] || !wannawin && l[0])
    cout << 1 << " ";
  else
    cout << 0 << " ";
  if (wannalose && l[0] || !wannalose && w[0])
    cout << 1 << " ";
  else
    cout << 0 << " ";
  return 0;
}

```