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 int maxabn = 1e5 + 79, sqrtn = 350, rvsqrtn = maxabn / sqrtn + 79;
const long long inf = 1e18;
long long divup(long long a, long long b) { return a / b + ((a % b) > 0); }
int n, w;
vector<int> a(maxabn), b(maxabn);
vector<long long> coef(rvsqrtn, 0);
vector<vector<int> > v(maxabn);
class linear_function {
 public:
  long long a, b;
  linear_function(long long A, long long B) : a(A), b(B) {}
  linear_function() {}
  long long intersection(linear_function g) {
    if (g.a == a) return b <= g.b ? -inf : inf;
    return divup(b - g.b, g.a - a);
  }
  long long eval(long long point) { return a * point + b; }
};
vector<linear_function> f(maxabn, linear_function(0, 0));
class cht {
 public:
  long long l, r;
  vector<pair<long long, int> > lines;
  void insert(int i) {
    while (r &&
           f[lines[r - 1].second].intersection(f[i]) <= lines[r - 1].first) {
      r--;
    }
    if (r)
      lines[r] = {f[lines[r - 1].second].intersection(f[i]), i}, r++;
    else
      lines[r++] = {-inf, i};
  }
  int get(long long y) {
    while (l + 1 < r && lines[l + 1].first <= y) l++;
    return lines[l].second;
  }
  void build(int il, int ir) {
    l = 0, r = 0;
    for (int i = il; i < ir; i++) insert(i);
  }
  cht() : lines(sqrtn), l(0), r(0) {}
};
vector<cht> c(rvsqrtn);
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, w;
  cin >> n >> w;
  for (int i = 0; i < n; i++) cin >> a[i] >> b[i], v[b[i]].push_back(i);
  for (int i = 0; i < maxabn; i++) f[i].a = i;
  for (int i = 0; i < rvsqrtn; i++)
    c[i].build(i * sqrtn, min(maxabn, (i + 1) * sqrtn));
  int maxb = *max_element(b.begin(), b.end()), adds = n;
  for (int i = 0; i <= maxb + 1; i++) {
    pair<long long, int> ans(0, 0);
    for (int j = 0; j < rvsqrtn; j++) {
      int nw = c[j].get(coef[j]);
      ans = max(ans, {f[nw].eval(coef[j]), nw});
    }
    cout << adds * 1ll * i * 1ll * w + ans.first << " " << ans.second << "\n";
    for (int j : v[i]) {
      int block = a[j] / sqrtn;
      for (int k = 0; k < block; k++) coef[k]++;
      for (int k = block * sqrtn; k <= a[j]; k++) f[k].b += k;
      c[block].build(block * sqrtn, min(maxabn, (block + 1) * sqrtn));
      adds--;
    }
  }
  return 0;
}