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 MAX = 100200;
const int BLOCK_SIZE = 300;
const int BLOCK_CNT = MAX / BLOCK_SIZE;
pair<int, int> user[MAX];
int sz[BLOCK_CNT];
int st[BLOCK_CNT][BLOCK_SIZE + 10];
long double sx[BLOCK_CNT][BLOCK_SIZE + 10];
int ptr[BLOCK_CNT];
long long bmax[BLOCK_CNT];
int bid[BLOCK_CNT];
int badd[BLOCK_CNT];
int a[MAX];
long double intersect(int i, int j) {
  return 1.0 * ((long long)i * a[i] - (long long)j * a[j]) / (j - i);
}
long long pay[MAX];
int opt[MAX];
int main() {
  int n, w;
  scanf("%d %d", &n, &w);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &user[i].second, &user[i].first);
  }
  sort(user, user + n);
  int maxbi = user[n - 1].first;
  for (int i = 0; i < MAX; i++) {
    a[i] = 0;
  }
  for (int b = 0; b < BLOCK_CNT; b++) {
    bmax[b] = 0;
    bid[b] = b * BLOCK_SIZE;
    badd[b] = 0;
  }
  int j = 0;
  for (int C = 0; C <= maxbi + 1; C++) {
    while (j < n) {
      if (user[j].first >= C) {
        break;
      }
      int pos = user[j].second;
      for (int b = 0; b < BLOCK_CNT; b++) {
        int from = b * BLOCK_SIZE;
        int to = from + BLOCK_SIZE;
        if (pos >= to) {
          badd[b]++;
          while (ptr[b] < sz[b] && badd[b] > sx[b][ptr[b]]) {
            ptr[b]++;
          }
          int q = st[b][ptr[b]];
          bmax[b] = (long long)q * (a[q] + badd[b]);
          bid[b] = q;
        } else {
          for (int i = from; i < to; i++) {
            a[i] += badd[b];
          }
          for (int i = from; i <= pos; i++) {
            a[i]++;
          }
          badd[b] = 0;
          sz[b] = 0;
          for (int i = from; i < to; i++) {
            while (sz[b] >= 2) {
              long double u = intersect(i, st[b][sz[b]]);
              if (u < sx[b][sz[b] - 1]) {
                sz[b]--;
              } else {
                break;
              }
            }
            st[b][++sz[b]] = i;
            if (sz[b] >= 2) {
              sx[b][sz[b] - 1] = intersect(i, st[b][sz[b] - 1]);
            }
          }
          ptr[b] = 1;
          while (ptr[b] < sz[b] && 0 > sx[b][ptr[b]]) {
            ptr[b]++;
          }
          int q = st[b][ptr[b]];
          bmax[b] = (long long)q * a[q];
          bid[b] = q;
          break;
        }
      }
      j++;
    }
    pay[C] = -1;
    opt[C] = -1;
    for (int b = 0; b < BLOCK_CNT; b++) {
      if (bmax[b] > pay[C]) {
        pay[C] = bmax[b];
        opt[C] = bid[b];
      }
    }
    pay[C] += C * 1LL * w * (n - j);
  }
  for (int C = 0; C <= maxbi + 1; C++) {
    printf("%I64d %d\n", pay[C], opt[C]);
  }
  return 0;
}