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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int mod = 1e9 + 7;
const long double Pi = acos(-1.0);
using ll = long long;
using ii = pair<int, int>;
const int mxN = 1e5 + 5;
const int blkSz = 200;
const int blkNum = (mxN + blkSz - 1) / blkSz;
ii arr[mxN];
ll n;
vector<ii> tsunami[blkNum];
ll lz[blkNum];
ll freq[mxN];
pair<ll, ll> qry(int l, int r) {
  r++;
  pair<ll, int> ret = make_pair(-1e5, 0);
  for (; l < r && l % blkSz != 0; l++) {
    ret = max(ret, make_pair(freq[l], l));
  }
  for (; l / blkSz != r / blkSz; l += blkSz) {
    int idx = tsunami[l / blkSz].back().second;
    ll advance = lz[l / blkSz];
    ll val = freq[idx] + advance * 1ll * idx;
    ret = max(ret, make_pair(val, idx));
  }
  for (; l < r; l++) {
    ret = max(ret, make_pair(freq[l], l));
  }
  return ret;
}
void calcArray(ll idx) {
  ll l = idx * blkSz, r = l + blkSz - 1;
  tsunami[idx].clear();
  pair<ll, ll> mx;
  bool f = false;
  for (ll i = l; i <= r; i++) {
    freq[i] += lz[idx] * 1ll * i;
    if (!f) mx = {freq[i], i}, f = 1;
    mx = max(mx, {freq[i], i});
  }
  lz[idx] = 0;
  tsunami[idx].push_back({0, mx.second});
  for (ll i = mx.second + 1; i <= r; i++) {
    ll j = 0;
    while (!tsunami[idx].empty()) {
      ll idx2 = tsunami[idx].back().second;
      j = (freq[idx2] - freq[i] + (i - idx2 - 1)) / (i - idx2);
      if (j > tsunami[idx].back().first) {
        break;
      }
      tsunami[idx].pop_back();
    }
    tsunami[idx].push_back({j, i});
  }
  reverse(tsunami[idx].begin(), tsunami[idx].end());
}
void updPart(int l, int r) {
  for (int i = l; i <= r; i++) freq[i] += i;
  calcArray(l / blkSz);
}
void updKollo(int idx) {
  lz[idx]++;
  while (tsunami[idx].size() > 1) {
    auto nxt = tsunami[idx][tsunami[idx].size() - 2];
    if (nxt.first <= lz[idx]) {
      tsunami[idx].pop_back();
    } else
      break;
  }
}
void upd(int l, int r) {
  if (r / blkSz == l / blkSz) {
    updPart(l, r);
    return;
  }
  r++;
  if (l % blkSz != 0) {
    updPart(l, (l + blkSz - 1) / blkSz - 1);
  }
  for (; l / blkSz != r / blkSz; l += blkSz) updKollo(l / blkSz);
  if (l != r) {
    updPart(l, r - 1);
  }
}
int main(int argc, char** argv) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ll w;
  cin >> n >> w;
  int mx = 0;
  for (ll i = 0; i < n; i++) {
    cin >> arr[i].second >> arr[i].first;
    mx = max(mx, arr[i].first);
  }
  for (ll i = 0; i * blkSz < mxN; i++) calcArray(i);
  sort(arr, arr + n);
  for (ll c = 0, j = 0; c <= mx + 1; c++) {
    while (j < n && arr[j].first < c) {
      upd(0, arr[j].second);
      j++;
    }
    ll freeCost = (n - j) * 1ll * c * w;
    auto ans = qry(0, 100000);
    cout << freeCost + ans.first << ' ' << ans.second << '\n';
  }
  return 0;
}