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 MAXN = 100005;
const int MAXQ = 1500;
const long long inf = 1000000005;
struct customer {
  long long a, b;
};
bool compare(customer X, customer Y) { return X.b < Y.b; }
long long gcd(long long a, long long b) {
  if (b > a) swap(a, b);
  while (b > 0) {
    a = a % b;
    swap(a, b);
  }
  return a;
}
struct rational {
  long long n, m;
  rational() { m = 1; };
  rational(int _n) {
    n = _n;
    m = 1;
  }
  void normalize() {
    if (m < 0) {
      n = -n;
      m = -m;
    }
  }
};
bool operator<(rational X, rational Y) { return (X.n * Y.m) < (X.m * Y.n); }
bool operator<=(rational X, rational Y) { return (X.n * Y.m) <= (X.m * Y.n); }
rational operator+(rational X, rational Y) {
  rational R;
  R.n = (X.n * Y.m) + (X.m * Y.n);
  R.m = X.m * Y.m;
  R.normalize();
  return R;
}
int Integer(rational X) { return X.n / X.m; }
struct segment {
  long long k, b;
  rational l, r;
  segment() {}
  segment(rational _l, rational _r, long long _k, long long _b) {
    l = _l;
    r = _r;
    k = _k;
    b = _b;
  }
};
int intersection(segment A, segment B) {
  rational P;
  P.n = B.b - A.b;
  P.m = A.k - B.k;
  P.normalize();
  if (A.l < P && P <= A.r && B.l <= P && P < B.r) return 2;
  if (B.l <= P && P < B.r) return 1;
  return 0;
}
rational GetPoint(segment A, segment B) {
  rational P;
  P.n = B.b - A.b;
  P.m = A.k - B.k;
  P.normalize();
  return P;
}
long long d[MAXN], k[MAXN];
vector<segment> S[MAXQ][MAXQ / 2];
void GetEnvelope(int v, int l, int r, int ind) {
  S[ind][v].clear();
  if (l == r) {
    S[ind][v].push_back(segment(rational(-inf), rational(inf), k[l], d[l]));
    return;
  }
  int mid = (l + r) / 2;
  GetEnvelope(2 * v, l, mid, ind);
  GetEnvelope(2 * v + 1, mid + 1, r, ind);
  int pntA = 0, pntB = 0;
  while (intersection(S[ind][2 * v][pntA], S[ind][2 * v + 1][pntB]) != 2) {
    if (intersection(S[ind][2 * v][pntA], S[ind][2 * v + 1][pntB]) == 1)
      pntA++;
    else
      pntB++;
  }
  for (int i = 0; i < pntA; i++) S[ind][v].push_back(S[ind][2 * v][i]);
  rational Px = GetPoint(S[ind][2 * v][pntA], S[ind][2 * v + 1][pntB]);
  S[ind][v].push_back(segment(S[ind][2 * v][pntA].l, Px, S[ind][2 * v][pntA].k,
                              S[ind][2 * v][pntA].b));
  S[ind][v].push_back(segment(Px, S[ind][2 * v + 1][pntB].r,
                              S[ind][2 * v + 1][pntB].k,
                              S[ind][2 * v + 1][pntB].b));
  for (int i = pntB + 1; i < S[ind][2 * v + 1].size(); i++)
    S[ind][v].push_back(S[ind][2 * v + 1][i]);
}
struct Block {
  int Size, pnt, Left, Right, ind;
  rational x;
  long long price;
  Block(){};
  Block(int l, int r, int _ind) {
    Size = r - l + 1;
    x = rational(0);
    Left = l;
    Right = r;
    ind = _ind;
    for (int i = l; i <= r; i++) {
      d[i] = 0;
      k[i] = i;
    }
    GetEnvelope(1, Left, Right, ind);
    pnt = 0;
    while (S[ind][1][pnt].r < x) pnt++;
    price = 0;
  }
  void Modify(int PrefSize) {
    if (PrefSize == Size) {
      x = x + 1;
      while (S[ind][1][pnt].r < x) pnt++;
    } else {
      for (int i = Left; i <= Right; i++) {
        d[i] += Integer(x) * k[i];
        if (i - Left + 1 <= PrefSize) d[i] += k[i];
      }
      GetEnvelope(1, Left, Right, ind);
      pnt = 0;
      x = rational(0);
      while (S[ind][1][pnt].r < x) pnt++;
    }
  }
  long long GetMax() {
    price = S[ind][1][pnt].k;
    return (S[ind][1][pnt].k * Integer(x)) + S[ind][1][pnt].b;
  }
};
customer Cust[MAXN];
Block B[MAXQ];
long long N, w, MPrice, MAns;
int main() {
  scanf("%I64d %I64d", &N, &w);
  MPrice = 0;
  MAns = 0;
  for (int i = 1; i <= N; i++) {
    scanf("%I64d %I64d", &Cust[i].a, &Cust[i].b);
    MPrice = max(MPrice, Cust[i].a);
    MAns = max(MAns, Cust[i].b + 1);
  }
  sort(Cust + 1, Cust + N + 1, compare);
  int q = int(0.4 * sqrt(MPrice));
  int pnt = 1;
  int r = 0;
  int K = 0;
  while (r < MPrice) {
    r = pnt + q;
    if (MPrice - r < 5) r = MPrice;
    K++;
    B[K] = Block(pnt, r, K);
    pnt += q + 1;
  }
  long long delta = 0;
  long long j = 1;
  long long res = 0;
  int best = 0;
  for (long long i = 0; i <= MAns; i++) {
    if (i > 0) delta -= (N - j + 1) * (i - 1) * w;
    bool flag = false;
    while (Cust[j].b == i - 1 && j <= N) {
      flag = true;
      int Inc = Cust[j].a;
      j++;
      int p = 1;
      while (Inc > 0) {
        B[p].Modify(min(Inc, B[p].Size));
        Inc -= min(Inc, B[p].Size);
        p++;
      }
    }
    delta += (N - j + 1) * (i)*w;
    if (flag) {
      res = 0;
      best = 0;
      for (int p = 1; p <= K; p++) {
        long long x = B[p].GetMax();
        if (res < x) {
          res = x;
          best = B[p].price;
        }
      }
    }
    printf("%I64d", delta + res);
    printf(" ");
    printf("%d", best);
    printf("\n");
  }
  return 0;
}