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;
template <class T>
inline bool checkMax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T, typename... Args>
inline void checkMax(T &a, const Args... arg) {
  checkMax(a, max(arg...));
}
template <class T>
inline bool checkMin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename... Args>
inline void checkMin(T &a, const Args... arg) {
  checkMin(a, min(arg...));
}
const int INF = 0x3f3f3f3f;
const long long llINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e5 + 5;
int n, w;
int a[MAXN], b[MAXN], ord[MAXN];
struct Block {
  static const int MAXB = 405;
  int S, tot, L[MAXB], R[MAXB], tag[MAXN], q[MAXB][MAXB], head[MAXB],
      tail[MAXB];
  long long val[MAXN];
  void init(int n) {
    S = sqrt(n);
    for (int i = 1; i <= n; i += S) L[++tot] = i, R[tot] = min(i + S - 1, n);
    for (int i = 1; i <= tot; i++) head[i] = 1, tail[i] = 0;
  }
  double slope(int i, int j) {
    return (double)(val[i] - val[j]) / (double)(j - i);
  }
  bool cmp1(int a, int b, int i) {
    return slope(b, i) < slope(a, b);
    return (long long)(val[i] - val[b]) * (a - i) >
           (long long)(val[b] - val[a]) * (b - a);
  }
  bool cmp2(int a, int b, int k) {
    return slope(a, b) <= k;
    return (val[b] - val[a]) >= (long long)k * (a - b);
  }
  void update(int t, int k) {
    while (head[t] < tail[t] && cmp2(q[t][head[t]], q[t][head[t] + 1], k))
      head[t] += 1;
  }
  void rebuild(int t) {
    head[t] = 1;
    tail[t] = 0;
    for (int i = L[t]; i <= R[t]; i++) {
      while (head[t] < tail[t] && cmp1(q[t][tail[t] - 1], q[t][tail[t]], i))
        tail[t] -= 1;
      q[t][++tail[t]] = i;
    }
    update(t, 0);
  }
  void modify(int x) {
    if (x <= 0) return;
    int t = (x - 1) / S + 1;
    for (int i = 1; i < t; i++) tag[i] += 1, update(i, tag[i]);
    for (int i = L[t]; i <= R[t]; i++) val[i] += (long long)i * tag[t];
    tag[t] = 0;
    for (int i = L[t]; i <= x; i++) val[i] += i;
    rebuild(t);
  }
  pair<long long, int> query() {
    pair<long long, int> ans(-1, 0);
    for (int i = 1; i <= tot; i++) {
      int x = q[i][head[i]];
      checkMax(ans, make_pair(val[x] + (long long)x * tag[i], x));
    }
    return ans;
  }
} B;
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]), ord[i] = i;
  int maxa = *max_element(a + 1, a + 1 + n);
  B.init(maxa);
  int maxb = *max_element(b + 1, b + 1 + n);
  sort(ord + 1, ord + 1 + n,
       [](const int &x, const int &y) { return b[x] < b[y]; });
  for (int i = 0, j = 1; i <= maxb + 1; i++) {
    while (j <= n && b[ord[j]] < i) B.modify(a[ord[j]]), j += 1;
    pair<long long, int> ans = B.query();
    printf("%lld %d\n", ans.first + (long long)w * i * (n - j + 1), ans.second);
  }
  return 0;
}