Problem: All modern mobile applications are divided into free and paid. Even a single application developers often release two versions: a paid version without ads and a free version with ads.

<image>

Suppose that a paid version of the app costs p (p is an integer) rubles, and the free version of the application contains c ad banners. Each user can be described by two integers: ai — the number of rubles this user is willing to pay for the paid version of the application, and bi — the number of banners he is willing to tolerate in the free version.

The behavior of each member shall be considered strictly deterministic:

  * if for user i, value bi is at least c, then he uses the free version, 
  * otherwise, if value ai is at least p, then he buys the paid version without advertising, 
  * otherwise the user simply does not use the application. 



Each user of the free version brings the profit of c × w rubles. Each user of the paid version brings the profit of p rubles.

Your task is to help the application developers to select the optimal parameters p and c. Namely, knowing all the characteristics of users, for each value of c from 0 to (max bi) + 1 you need to determine the maximum profit from the application and the corresponding parameter p.

Input

The first line contains two integers n and w (1 ≤ n ≤ 105; 1 ≤ w ≤ 105) — the number of users and the profit from a single banner. Each of the next n lines contains two integers ai and bi (0 ≤ ai, bi ≤ 105) — the characteristics of the i-th user.

Output

Print (max bi) + 2 lines, in the i-th line print two integers: pay — the maximum gained profit at c = i - 1, p (0 ≤ p ≤ 109) — the corresponding optimal app cost. If there are multiple optimal solutions, print any of them.

Examples

Input

2 1
2 0
0 2


Output

0 3
3 2
4 2
2 2


Input

3 1
3 1
2 2
1 3


Output

0 4
3 4
7 3
7 2
4 2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
const long long SQ = 340;
vector<int> e[MAXN];
vector<pair<long long, long long> > d[SQ];
int a[MAXN];
int b[MAXN];
int k[SQ][SQ];
int p[SQ];
int lazy[SQ];
void relax(long long id) {
  p[id] = 0;
  d[id].clear();
  d[id].push_back(make_pair(0, 0));
  k[id][0] += lazy[id];
  for (long long i = 1; i < SQ; i++) {
    k[id][i] += lazy[id];
    while (!d[id].empty()) {
      long long t =
          max(0LL, (long long)(ceil(((k[id][d[id].back().second] - k[id][i]) *
                                         (id * SQ + d[id].back().second) -
                                     k[id][i] * (i - d[id].back().second)) /
                                    (long double)(i - d[id].back().second))));
      if (d[id].back().first >= t) {
        d[id].pop_back();
      } else {
        break;
      }
    }
    if (d[id].empty()) {
      d[id].push_back(make_pair(0, i));
    } else {
      d[id].push_back(make_pair(
          max(0LL, (long long)(ceil(((k[id][d[id].back().second] - k[id][i]) *
                                         (id * SQ + d[id].back().second) -
                                     k[id][i] * (i - d[id].back().second)) /
                                    (long double)(i - d[id].back().second)))),
          i));
    }
  }
  lazy[id] = 0;
}
void update(int r) {
  for (int i = 0; (i + 1) * SQ - 1 < r; i++) {
    lazy[i]++;
    while (p[i] != (long long)(d[i].size()) - 1 &&
           d[i][p[i] + 1].first <= lazy[i]) {
      p[i]++;
    }
  }
  for (int i = (r / SQ) * SQ; i <= r; i++) {
    k[r / SQ][i - ((r / SQ) * SQ)]++;
  }
  relax(r / SQ);
  return;
}
pair<long long, long long> get_ans() {
  pair<long long, long long> res = make_pair(0, 0);
  for (long long i = 0; i < SQ; i++) {
    res = max(res, make_pair((d[i][p[i]].second + i * SQ) *
                                 (k[i][d[i][p[i]].second] + lazy[i]),
                             i * SQ + d[i][p[i]].second));
  }
  return res;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  long long n, w;
  cin >> n >> w;
  for (int i = 0; i < SQ; i++) {
    p[i] = 0;
    d[i].push_back(make_pair(0, SQ - 1));
  }
  int z = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    e[b[i]].push_back(i);
    z = max(z, b[i]);
  }
  long long num = n;
  for (int i = 0; i <= z + 1; i++) {
    pair<long long, long long> res = get_ans();
    cout << res.first + num * i * w << " " << res.second << endl;
    for (int j = 0; j < e[i].size(); j++) {
      update(a[e[i][j]]);
      num--;
    }
  }
}