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 comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  char c = getchar();
  long long su = 0, f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) su = su * 10 + c - '0';
  return su * f;
}
inline void wr(long long x) {
  if (x < 0) {
    putchar('-');
    wr(-x);
    return;
  }
  if (x >= 10) wr(x / 10);
  putchar(x % 10 + '0');
}
inline void wri(long long x) {
  wr(x);
  putchar(' ');
}
inline void wrn(long long x) {
  wr(x);
  putchar('\n');
}
inline void wrn(long long x, long long y) {
  wri(x);
  wrn(y);
}
inline void wrn(long long x, long long y, long long z) {
  wri(x);
  wrn(y, z);
}
pair<int, int> z[500055];
int n, m, f[500055], su2[500055], su1[500055], vis[500055], ku, kz, w, nu, ans2;
long long ans[500055], ans1, g[500055], yk;
bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
void cg(int x) {
  f[x] = 0;
  for (int i = (x * ku); i < (x * ku + ku); i++) {
    su2[i] += su1[x];
    if (!vis[i]) continue;
    if (1ll * i * su2[i] >= 1ll * f[x] * su2[f[x]]) {
      f[x] = i;
      g[x] = 1000000005;
    } else if (f[x] && su2[i])
      g[x] =
          min(g[x], (1ll * f[x] * su2[f[x]] - 1ll * i * su2[i]) / (i - f[x]));
  }
  ans[x] = 1ll * f[x] * su2[f[x]];
  su1[x] = 0;
}
void ad(int x) {
  int t = x / ku;
  vis[x]++;
  for (int i = (0); i <= (t - 1); i++) {
    su1[i]++;
    ans[i] += f[i];
    if (su1[i] > g[i]) cg(i);
  }
  for (int i = (t * ku); i < (t * ku + ku); i++) {
    su2[i] += su1[t];
    if (i <= x) su2[i]++;
  }
  su1[t] = 0;
  cg(t);
  yk = 0;
  ans2 = 0;
  for (int i = (0); i <= (kz); i++) {
    if (ans[i] > yk) yk = ans[i], ans2 = f[i];
  }
}
signed main() {
  n = read();
  w = read();
  int mx = 0;
  for (int i = (1); i <= (n); i++)
    mx = max(mx, z[i].first = read()), z[i].second = read();
  sort(z + 1, z + n + 1, cmp);
  ku = sqrt(100000);
  kz = mx / ku;
  int t1 = 1;
  nu = n;
  ans2 = 0;
  for (int i = (0); i <= (kz); i++) g[i] = 1000000005;
  for (int i = (0); i <= (z[n].second + 1); i++) {
    for (; t1 <= n && z[t1].second < i; t1++) {
      ad(z[t1].first);
      nu--;
    }
    ans1 = 1ll * nu * i * w + yk;
    wrn(ans1, ans2);
  }
  return 0;
}