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;
struct Vector {
  long long x, y;
  Vector(long long _x = 0, long long _y = 0) {
    x = _x;
    y = _y;
  }
  Vector operator+(Vector a) const { return Vector(x + a.x, y + a.y); }
  Vector operator+=(Vector a) { return *this = *this + a; }
  Vector operator-(Vector a) const { return Vector(x - a.x, y - a.y); }
  Vector operator-=(Vector a) { return *this = *this - a; }
  Vector operator*(double p) const { return Vector(x * p, y * p); }
  Vector operator*=(double p) { return *this = *this * p; }
  bool operator<(const Vector a) const {
    if (x == a.x) return y < a.y;
    return x < a.x;
  }
  double len() const { return sqrt(x * x + y * y); }
  double angle() const { return atan2(y, x); }
};
inline long long cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
const int maxn = 1e5 + 5;
const int SZ = 350;
long long s[maxn];
Vector p[maxn];
struct Block {
  int l, r, K, cur, top;
  Vector convex[400];
  inline long long val(int id) { return convex[id].y + K * convex[id].x; }
  inline void build() {
    for (int i = l; i <= r; ++i) s[i] += 1LL * i * K, p[i] = Vector(i, s[i]);
    K = cur = top = 0;
    for (int i = l; i <= r; ++i) {
      while (top >= 2 &&
             cross(convex[top - 1] - p[i], convex[top - 2] - p[i]) <= 0)
        --top;
      convex[top++] = p[i];
    }
  }
  inline void add(int x) {
    for (int i = l; i <= x; ++i) s[i] += i;
  }
  inline pair<long long, long long> ask() {
    while (cur + 1 < top && val(cur + 1) >= val(cur)) ++cur;
    return make_pair(convex[cur].x, val(cur));
  }
  inline void init(int L, int R) {
    l = L;
    r = R;
    build();
  }
} bk[400];
inline void updata(int x) {
  if (!x) return;
  int i, j;
  for (i = 1, j = 0; i + SZ - 1 <= x; i += SZ, ++j) ++bk[j].K;
  if (i > x) return;
  bk[j].add(x);
  bk[j].build();
}
inline pair<long long, long long> Query() {
  pair<long long, long long> res = make_pair(0, 0), tmp;
  for (int i = 1, j = 0; i <= 100000; i += SZ, ++j) {
    tmp = bk[j].ask();
    if (tmp.second > res.second) res = tmp;
  }
  return res;
}
pair<int, int> per[maxn];
int main() {
  for (int j = 0, i = 1; i <= 100000; i += SZ, ++j) {
    int l = i, r = min(100000, i + SZ - 1);
    bk[j].init(l, r);
  }
  int n, w;
  scanf("%d%d", &n, &w);
  for (int i = 0; i < n; ++i) scanf("%d%d", &per[i].second, &per[i].first);
  sort(per, per + n);
  int N = per[n - 1].first + 1;
  for (int j = 0, i = 0; i <= N; ++i) {
    for (; j < n && per[j].first < i; ++j) updata(per[j].second);
    pair<long long, long long> ans = Query();
    ans.second += 1LL * i * w * (n - j);
    printf("%I64d %I64d\n", ans.second, ans.first);
  }
  return 0;
}