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 N = 100 * 1000 + 100;
const int SQ = 317;
int n;
long long w;
pair<long long, long long> h[N];
pair<long long, long long> maxi[SQ][SQ];
long long m[N];
long long t[N];
vector<pair<long long, long long> > tmp;
vector<pair<long long, long long> > tmP;
void build(int x) {
  tmp.clear();
  tmP.clear();
  for (int i = x * SQ; i < min(N, x * SQ + SQ); ++i)
    tmp.push_back(make_pair(m[i], i));
  sort(tmp.begin(), tmp.end());
  reverse(tmp.begin(), tmp.end());
  int t = -1;
  for (int i = 0; i < ((int)tmp.size()); ++i)
    if (!i || (tmp[t].first > tmp[i].first && tmp[i].second > tmp[t].second))
      tmP.push_back(tmp[i]), t = i;
  tmp.clear();
  for (int i = 0; i < ((int)tmP.size()); ++i) {
    while (((int)tmp.size()) > 1) {
      pair<long long, long long> a = tmp.back();
      pair<long long, long long> b = tmp[((int)tmp.size()) - 2];
      pair<long long, long long> c = tmP[i];
      if ((a.first - c.first) * (c.second - b.second) <=
          (b.first - c.first) * (c.second - a.second))
        tmp.pop_back();
      else
        break;
    }
    tmp.push_back(tmP[i]);
  }
  int k = 0;
  for (int i = 0; i < SQ; ++i) {
    while (k + 1 < ((int)tmp.size()) &&
           tmp[k].second * i + tmp[k].first <
               tmp[k + 1].second * i + tmp[k + 1].first)
      k++;
    maxi[x][i].first = tmp[k].second * i + tmp[k].first;
    maxi[x][i].second = tmp[k].second;
  }
}
void add(int x) {
  int y = 0;
  while (y * SQ < x - x % SQ) {
    t[y]++;
    if (t[y] == SQ) {
      for (int i = y * SQ; i < y * SQ + SQ; ++i) m[i] += (i * t[y]);
      build(y);
      t[y] = 0;
    }
    y++;
  }
  for (int i = y * SQ; i <= x; ++i) m[i] += i;
  for (int i = y * SQ; i < min(y * SQ + SQ, N); ++i) m[i] += (i * t[y]);
  t[y] = 0;
  build(y);
}
pair<long long, long long> get() {
  pair<long long, long long> ans = make_pair(0, 0);
  for (int i = 0; i * SQ < N; ++i) ans = max(ans, maxi[i][t[i]]);
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> w;
  for (int i = 0; i < n; ++i) cin >> h[i].second >> h[i].first;
  sort(h, h + n);
  long long k = 0;
  for (int i = 0; i <= h[n - 1].first + 1; ++i) {
    while (k < n && h[k].first < i) {
      add(h[k].second);
      k++;
    }
    pair<long long, long long> ans = get();
    cout << (n - k) * i * w + ans.first << " " << ans.second << '\n';
  }
  return 0;
}