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 GCC optimize("O2")
using namespace std;
const int N = 1e6 + 10;
const long long mod = 1e9 + 7;
const long long mod2 = 998244353;
const long long inf = 8e18;
const int LOG = 22;
const int SQ = 320;
long long pw(long long a, long long b, long long M) {
  return (!b ? 1
             : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M
                      : pw(a * a % M, b / 2, M)));
}
int n, m, Mx, B, w, res, head[N], nxt[N], to[N], cnt;
long long d[N];
inline void insert(int u, int v) {
  nxt[++cnt] = head[u];
  to[cnt] = v;
  head[u] = cnt;
}
inline long double slope(int i, int j) {
  return (long double)(d[i] - d[j]) / (j - i);
}
struct node {
  int q[SQ], l, r, C;
  void build(int L, int R) {
    l = 0;
    r = -1;
    for (int i = L; i <= R; i++) {
      while (r - l > 0 && slope(q[r - 1], q[r]) > slope(q[r], i)) {
        r--;
      }
      r++;
      q[r] = i;
    }
  }
  long long getmax() {
    if (l > r) return 0;
    while (r - l > 0 && slope(q[l], q[l + 1]) < C) {
      l++;
    }
    return d[q[l]] + 1ll * q[l] * C;
  }
};
node s[SQ];
int main() {
  scanf("%d%d", &n, &w);
  for (int a, b, i = 1; i <= n; ++i) {
    scanf("%d%d", &a, &b);
    insert(b, a);
    if (b + 1 > Mx) Mx = b + 1;
    if (a > m) m = a;
  }
  B = ceil(sqrt(m));
  for (int i = 1; i <= (m - 1) / B + 1; i++) {
    s[i].build((i - 1) * B + 1, min(i * B, m));
  }
  for (int k = 0; k <= Mx; k++) {
    if (k) {
      for (int p, i = head[k - 1]; i; i = nxt[i]) {
        n--, p = to[i];
        for (int j = 1; j <= p / B; j++) {
          s[j].C += 1;
        }
        for (int j = p / B * B + 1; j <= p; j++) {
          d[j] += j;
        }
        s[p / B + 1].build(p / B * B + 1, min((p / B + 1) * B, m));
      }
    }
    for (int i = res = 1; i <= (m - 1) / B + 1; i++) {
      if (s[res].getmax() < s[i].getmax()) {
        res = i;
      }
    }
    printf("%lld %d\n", 1ll * k * n * w + s[res].getmax(), s[res].q[s[res].l]);
  }
  return 0;
}