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 warning(disable : 4996)
template <typename T>
T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T max(T x, T y) {
  return x > y ? x : y;
}
const long long MAXN = 100005;
const long long B = 1005;
struct line {
  double k;
  double b;
  line(double K = 0, double B = 0) {
    k = K;
    b = B;
  }
  double calc(double x) { return k * x + b; }
};
double cross(line x, line y) { return (y.b - x.b) / (x.k - y.k); }
struct hull {
  std::vector<line> L;
  std::vector<line> Q;
  long long add, cur;
  void build() {
    Q.clear();
    Q.push_back(L[0]);
    for (long long i = 1; i < L.size(); i++) {
      line t = L[i];
      while (Q.size() >= 2 && cross(t, Q[Q.size() - 2]) <
                                  cross(Q[Q.size() - 1], Q[Q.size() - 2]))
        Q.pop_back();
      Q.push_back(t);
    }
    add = cur = 0;
    while (cur + 1 < Q.size() && Q[cur + 1].calc(add) > Q[cur].calc(add)) cur++;
  }
  void ADD(long long x) {
    add += x;
    while (cur + 1 < Q.size() && Q[cur + 1].calc(add) > Q[cur].calc(add)) cur++;
  }
  void update(long long l, long long r, long long x) {
    for (long long i = 0; i < L.size(); i++)
      L[i].b += add * L[i].k + (i >= l && i <= r) * x * L[i].k;
    build();
  }
  std::pair<double, double> maximum() {
    return std::make_pair(Q[cur].calc(add), Q[cur].k);
  }
};
struct user {
  long long a;
  long long b;
  bool operator<(user x) const { return b < x.b; }
};
long long N, W;
user u[MAXN];
long long mxa, mxb;
long long l[MAXN], r[MAXN], tot;
hull H[B];
void operate(long long L, long long R) {
  for (long long i = 1; i <= tot; i++) {
    if (l[i] >= L && r[i] <= R)
      H[i].ADD(1);
    else if (L >= l[i] && R <= r[i])
      H[i].update(L - l[i], R - l[i], 1);
    else if (L >= l[i] && L <= r[i] || R >= l[i] && R <= r[i])
      H[i].update(max(L, l[i]) - l[i], min(R, r[i]) - l[i], 1);
  }
}
std::pair<double, double> query() {
  std::pair<double, double> t(0, 0);
  for (long long i = 1; i <= tot; i++) t = std::max(t, H[i].maximum());
  return t;
}
void init() {
  scanf("%I64d %I64d", &N, &W);
  for (long long i = 1; i <= N; i++) {
    scanf("%I64d %I64d", &u[i].a, &u[i].b);
    mxa = max(mxa, u[i].a);
    mxb = max(mxb, u[i].b);
  }
  std::sort(u + 1, u + N + 1);
  for (long long x = 0, y; x <= mxa; x = y + 1) {
    y = min(x + B - 1, mxa);
    tot++;
    l[tot] = x, r[tot] = y;
  }
  for (long long i = 1; i <= tot; i++) {
    for (long long j = l[i]; j <= r[i]; j++) H[i].L.push_back(line(j, 0));
    H[i].build();
  }
}
void solve() {
  long long cur = 1;
  for (long long i = 0; i <= mxb + 1; i++) {
    while (cur <= N && u[cur].b < i) operate(0, u[cur].a), cur++;
    std::pair<double, double> t = query();
    printf("%I64d %I64d\n", (N - cur + 1) * W * i + (long long)t.first,
           (long long)t.second);
  }
}
void print() {
  printf("--------------------------------------\n");
  printf("%I64d %I64d\n", H[1].add, H[1].cur);
  for (long long i = 0; i < H[1].Q.size(); i++)
    printf("%lf %lf\n", H[1].Q[i].k, H[1].Q[i].b);
}
int main() {
  init();
  solve();
  return 0;
}