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;
const int N = 109395, SQ = 329;
struct CHT {
  pair<long long, pair<long long, long long> > A[SQ + 5];
  long long l = 0, r = 0, p = 0, INF = 1e18;
  inline void Add(pair<long long, long long> X) {
    while (r - l && Intersection(A[r - 1].second, X) <= A[r - 1].first) r--;
    if (r - l)
      A[r] = {Intersection(A[r - 1].second, X), X}, r++;
    else
      A[r++] = {-INF, X};
  }
  inline long long GetMax() {
    while (l + 1 < r && A[l + 1].first <= p) l++, A[l].first = -INF;
    return (A[l].second.first * p + A[l].second.second);
  }
  inline long long Intersection(pair<long long, long long> X,
                                pair<long long, long long> Y) {
    if (X.first == Y.first && X.second <= Y.second) return (-INF);
    if (X.first == Y.first) return (INF);
    return ((X.second - Y.second) / (Y.first - X.first)) +
           ((X.second - Y.second) % (Y.first - X.first) > 0);
  }
};
int n, W, MX, A[N];
vector<int> Q[N];
CHT C[SQ];
inline void Rebuild(int block) {
  C[block].l = C[block].r = 0;
  for (int i = block * SQ; i < (block + 1) * SQ; i++)
    C[block].Add({i, (long long)A[i] * i});
}
int main() {
  scanf("%d%d", &n, &W);
  for (int i = 0; i < n; i++) {
    int c, p;
    scanf("%d%d", &p, &c);
    Q[c + 1].push_back(p);
    MX = max(MX, c + 1);
  }
  for (int i = 0; i < SQ; i++) Rebuild(i);
  for (int i = 0; i <= MX; i++) {
    for (int p : Q[i]) {
      for (int j = 0; j < p / SQ; j++) C[j].p++;
      for (int j = p / SQ * SQ; j <= p; j++) A[j]++;
      Rebuild(p / SQ);
      n--;
    }
    int block = 0, id = 0;
    long long Mx = 0;
    for (int j = 0; j < SQ; j++)
      if (C[j].GetMax() > Mx) Mx = C[j].GetMax(), block = j;
    for (int j = block * SQ; j < (block + 1) * SQ; j++)
      if ((C[block].p + A[j]) * j == Mx) {
        id = j;
        break;
      }
    printf("%lld %d\n", Mx + (long long)n * W * i, id);
  }
  return 0;
}