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
#include <bits/stdc++.h>
using namespace std;
const int N = 112 * 1000;
const int BSIZE = 100;
const int BNUM = 1002;
long long best_gain[N];
int best_price[N];
int when_clean[N];
int bigger[N];
int num_guys[N];
void recalc(int b) {
  long long gcur = 0;
  int valid = N;
  int l = b * BSIZE;
  int r = l + BSIZE - 1;
  int p = l;
  int cust = bigger[b];
  for (int i = (r); i >= (l); --i) {
    cust += num_guys[i];
    if ((long long)cust * i > gcur) {
      gcur = (long long)cust * i;
      p = i;
    }
  }
  cust = bigger[b];
  for (int i = (r); i >= (p + 1); --i) {
    cust += num_guys[i];
    valid = (int)min((long long)valid, (gcur - (long long)cust * i) / (i - p));
  }
  best_gain[b] = gcur;
  best_price[b] = p;
  when_clean[b] = max(0, valid - 2);
}
void dodaj(int x) {
  int b = x / BSIZE;
  num_guys[x]++;
  recalc(b);
  for (int i = 0; i < (b); ++i) {
    bigger[i]++;
    if (when_clean[i] == 0)
      recalc(i);
    else {
      when_clean[i]--;
      best_gain[i] += best_price[i];
    }
  }
}
pair<long long, int> find_max() {
  long long res = 0;
  int p = 0;
  for (int i = 0; i < (BNUM); ++i)
    if (best_gain[i] > res) {
      res = best_gain[i];
      p = best_price[i];
    }
  return make_pair(res, p);
}
void init() {
  for (int i = 0; i < (BNUM); ++i) {
    best_gain[i] = best_price[i] = 0;
    when_clean[i] = N;
  }
}
int main() {
  init();
  int n, w;
  scanf("%d %d", &n, &w);
  vector<pair<int, int> > v;
  int mb = 0;
  for (int i = 0; i < (n); ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    mb = max(mb, b);
    v.push_back(make_pair(b, a));
  }
  sort(v.begin(), v.end());
  int pos = 0;
  for (int c = (0); c <= (mb + 1); ++c) {
    while (pos < (int)v.size() && v[pos].first < c) {
      dodaj(v[pos].second);
      pos++;
    }
    pair<long long, int> p = find_max();
    cout << (p.first + (long long)c * w * ((int)v.size() - pos)) << " "
         << p.second << endl;
  }
  return 0;
}
