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 char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline void read(int &x) {
  char c = nc(), b = 1;
  for (; !(c >= '0' && c <= '9'); c = nc())
    if (c == '-') b = -1;
  for (x = 0; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = nc())
    ;
  x *= b;
}
const int N = 100005;
int n, W;
int a[N], b[N];
int maxa = 0;
int idx[N];
inline bool cmp(int x, int y) { return b[x] < b[y]; }
const int BB = 505;
int B, cnt;
int pos[N];
int lp[BB], rp[BB];
long long c[N];
int tag[BB];
long long clk[BB];
int K[BB];
inline void Build() {
  B = (int)sqrt(maxa);
  for (int i = 0; i <= maxa; i++) pos[i] = i / B + 1;
  cnt = pos[maxa];
  for (int i = 1; i <= cnt; i++) lp[i] = (i - 1) * B, rp[i] = i * B - 1;
  rp[cnt] = maxa;
  for (int i = 1; i <= cnt; i++) {
    K[i] = lp[i];
    if (K[i] == rp[i])
      clk[i] = 1 << 30;
    else
      clk[i] = 1;
  }
}
inline void rebuild(int x, int l, int r) {
  long long maxv = -1, k = 0, t = 0;
  for (int i = lp[x]; i <= rp[x]; i++) {
    c[i] += tag[x];
    c[i] += (l <= i && i <= r);
    if (c[i] * i > maxv) maxv = c[i] * i, k = i;
  }
  K[x] = k;
  tag[x] = 0;
  clk[x] = 1 << 30;
  for (int i = k + 1; i <= rp[x]; i++)
    clk[x] = min(clk[x], (c[k] * k - c[i] * i) / (i - k) + 1);
}
inline void Add(int r) {
  int rb = pos[r];
  rebuild(rb, lp[rb], r);
  for (int i = 1; i < rb; i++) {
    tag[i]++;
    clk[i]--;
    if (!clk[i]) rebuild(i, 0, -1);
  }
}
long long ans = 0, p;
inline void Query() {
  ans = 0;
  p = 0;
  for (int i = 1; i <= cnt; i++)
    if ((c[K[i]] + tag[i]) * K[i] > ans)
      ans = (c[K[i]] + tag[i]) * K[i], p = K[i];
}
int main() {
  read(n);
  read(W);
  for (int i = 1; i <= n; i++)
    read(a[i]), read(b[i]), idx[i] = i, maxa = max(maxa, a[i]);
  Build();
  sort(idx + 1, idx + n + 1, cmp);
  int lim = b[idx[n]] + 1, pnt = 1;
  for (int c = 0; c <= lim; c++) {
    while (pnt <= n && c > b[idx[pnt]]) Add(a[idx[pnt]]), pnt++;
    Query();
    printf("%I64d %d\n", (long long)c * W * (n - pnt + 1) + ans, p);
  }
  return 0;
}