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 = 1e5 + 5, G = 321, nn = 100000;
int n, w;
int h[G], I, t[G], D[G][G], Id[N], tag[G];
long long ans, sum[N];
struct Data {
  int a, b;
} A[N];
bool operator<(Data a, Data b) { return a.b < b.b; }
void Ins(int x) {
  for (int i = 0; i < Id[x]; i++) {
    tag[i]++;
    for (; h[i] < t[i] &&
           sum[D[i][h[i]]] + (long long)tag[i] * D[i][h[i]] <
               sum[D[i][h[i] + 1]] + (long long)tag[i] * D[i][h[i] + 1];
         h[i]++)
      ;
  }
  int k = Id[x];
  for (int i = k * G; Id[i] == k; i++) {
    sum[i] += (long long)tag[k] * i;
    if (i <= x) sum[i] += i;
  }
  tag[k] = t[k] = 0;
  h[k] = 1;
  for (int i = k * G; Id[i] == k; i++) {
    for (; h[k] < t[k] && 1.0 * (sum[D[k][t[k]]] - sum[i]) / (i - D[k][t[k]]) <
                              1.0 * (sum[D[k][t[k] - 1]] - sum[D[k][t[k]]]) /
                                  (D[k][t[k]] - D[k][t[k] - 1]);
         t[k]--)
      ;
    D[k][++t[k]] = i;
  }
  for (; h[k] < t[k] && sum[D[k][h[k]]] < sum[D[k][h[k] + 1]]; h[k]++)
    ;
}
void Ask() {
  ans = 0;
  I = 0;
  for (int i = 0; i <= Id[nn]; i++)
    if (sum[D[i][h[i]]] + (long long)tag[i] * D[i][h[i]] > ans) {
      ans = sum[D[i][h[i]]] + (long long)tag[i] * D[i][h[i]];
      I = D[i][h[i]];
    }
}
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; i++) scanf("%d%d", &A[i].a, &A[i].b);
  sort(A + 1, A + n + 1);
  for (int i = 0; i <= nn; i++) Id[i] = i / G;
  Id[nn + 1] = -1;
  for (int i = 0; i <= Id[nn]; i++) {
    h[i] = t[i] = 1;
    D[i][1] = (i + 1) * G - 1;
  }
  D[Id[nn]][1] = nn;
  for (int i = 0, j = 1; i <= A[n].b + 1; i++) {
    for (; j <= n && A[j].b < i; j++) Ins(A[j].a);
    Ask();
    printf("%I64d %d\n", ans + (long long)(n - j + 1) * w * i, I);
  }
  return 0;
}