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 int Get() {
  int res = 0, q = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') q = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
  return res * q;
}
const double eps = 1e-12, pi = M_PI;
const int oo = (int)2e9, mod = (int)1e9 + 7;
const long long INF = (long long)1e17;
const int N = (int)1e5, T = 320;
typedef long long arrn[N + 10];
typedef long long arrt[T + 10];
long long i, j, k, p, n, m, w, mxa, mxb;
arrn A, B, ord;
struct block {
  arrt tx, ty, y;
  long long K, C, tot, btx, bty;
  inline long long Ky(long long x) { return K * tx[x] + ty[x]; }
  bool Leave(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - x2 * y1 <= 0;
  }
  void Build() {
    for (long long i = (0), end = (T - 1); i <= end; ++i) y[i] += K * i;
    K = tot = 0;
    for (long long i = (0), end = (T - 1); i <= end; ++i) {
      for (; tot > 1 && Leave(i - tx[tot], y[i] - ty[tot],
                              tx[tot] - tx[tot - 1], ty[tot] - ty[tot - 1]);
           --tot)
        ;
      tx[++tot] = i, ty[tot] = y[i];
    }
    btx = 0;
    for (long long i = (1), end = (tot); i <= end; ++i)
      if (ty[i] > ty[btx]) btx = i;
    bty = ty[btx] + C;
  }
  void Update() {
    ++K;
    for (; btx + 1 <= tot && Ky(btx + 1) > Ky(btx); ++btx)
      ;
    bty = Ky(btx) + C;
  }
} bl[T + 10];
void Init() {
  scanf(
      "%I64d"
      "%I64d"
      "\n",
      &n, &w);
  for (long long i = (1), end = (n); i <= end; ++i)
    scanf(
        "%I64d"
        "%I64d"
        "\n",
        A + i, B + i),
        mxa = ((mxa) > (A[i]) ? (mxa) : (A[i])),
        mxb = ((mxb) > (B[i]) ? (mxb) : (B[i])), ord[i] = i;
}
bool cmp(const long long &a, const long long &b) { return B[a] < B[b]; }
void Insert(long long x) {
  for (long long i = (0), end = (x / T - 1); i <= end; ++i)
    bl[i].C += T * i, bl[i].Update();
  long long block = x / T;
  for (long long j = (0), end = (x % T); j <= end; ++j)
    bl[block].y[j] += block * T + j;
  bl[block].Build();
}
void Calc() {
  sort(ord + 1, ord + n + 1, cmp);
  for (int c = 0, now = 1; c <= mxb + 1; ++c) {
    for (; now <= n && B[ord[now]] < c; ++now) Insert(A[ord[now]]);
    long long ansx = 0, ansy = 0;
    for (long long i = (0), end = (mxa / T); i <= end; ++i) {
      if (bl[i].bty > ansy)
        ansy = bl[i].bty, ansx = bl[i].tx[bl[i].btx] + i * T;
    }
    ansy += (n - now + 1) * c * w;
    printf(
        "%I64d"
        " "
        "%I64d"
        "\n",
        ansy, ansx);
  }
}
int main() {
  Init();
  Calc();
  return 0;
}