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;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
inline void writes(string s) { puts(s.c_str()); }
inline void writeln() { writes(""); }
inline void writei(int x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline void writell(long long x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
long long n, m, i, j, blk, id[200005], rem[200005], q_mx, q_id, mxa, c[200005],
    tag[200005];
struct ii {
  long long a, b;
} a[200005];
bool cmp(ii x, ii y) { return x.b < y.b; }
void rebuild(int x) {
  long long mxv = -1, mxid = 0, i;
  for ((i) = (blk * x); (i) <= (min(blk * x + blk - 1, mxa)); (i)++) {
    c[i] += tag[x];
    if (i * c[i] > mxv) {
      mxv = i * c[i];
      mxid = i;
    }
  }
  tag[x] = 0;
  id[x] = mxid;
  rem[x] = 0x1bbbbbbbbbbbbbbbll;
  for ((i) = (mxid + 1); (i) <= (min(blk * x + blk - 1, mxa)); (i)++) {
    rem[x] = min(rem[x], (c[mxid] * mxid - c[i] * i) / (i - mxid) + 1);
  }
}
void add(int x) {
  int bx = x / blk;
  while ((x + blk) / blk == bx + 1) {
    c[x]++;
    x--;
  }
  rebuild(bx);
  while (x >= 0) {
    tag[x / blk]++;
    rem[x / blk]--;
    if (rem[x / blk] == 0) rebuild(x / blk);
    x -= blk;
  }
}
void query() {
  q_mx = 0;
  q_id = 0;
  long long i;
  for ((i) = (0); (i) <= (mxa / blk); (i)++) {
    if ((c[id[i]] + tag[i]) * id[i] > q_mx) {
      q_mx = (c[id[i]] + tag[i]) * id[i];
      q_id = id[i];
    }
  }
}
int main() {
  read(n);
  read(m);
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    read(a[i].a);
    read(a[i].b);
    mxa = max(mxa, a[i].a);
  }
  sort(a + 1, a + n + 1, cmp);
  blk = sqrt(mxa);
  for ((i) = (0); (i) <= (mxa / blk); (i)++) {
    if (blk * i == min(blk * i + blk - 1, mxa))
      rem[i] = 0x1bbbbbbbbbbbbbbbll;
    else
      rem[i] = 1;
    id[i] = i * blk;
  }
  j = 1;
  for ((i) = (0); (i) <= (a[n].b + 1); (i)++) {
    while (j <= n && a[j].b < i) {
      add(a[j++].a);
    }
    query();
    printf("%I64d %I64d\n", (n - j + 1) * m * i + q_mx, q_id);
  }
  return 0;
}