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, Z = 317;
int n, w, freq[N], ans, mx;
long long val[N + 1];
vector<int> v[N + 1];
deque<int> q[N];
int get(int a, int b) {
  if (val[a] <= val[b]) return 0;
  long long temp = val[b] - val[a];
  return (temp + b - a - 1) / (b - a);
}
bool bad;
void build(int at) {
  deque<int>& q = ::q[at];
  q.clear();
  int to = min(N + 1, (at + 1) * Z);
  for (int i = at * Z; i < to; i++) {
    val[i] += i * 1LL * freq[at];
    while (q.size() > 1 && (val[q.back()] - val[q[q.size() - 2]]) * 1LL *
                                   (q[q.size() - 2] - i) >=
                               (val[i] - val[q[q.size() - 2]]) * 1LL *
                                   (q[q.size() - 2] - q.back()))
      q.pop_back();
    q.push_back(i);
  }
  freq[at] = 0;
}
int get() {
  int ret = 0;
  for (int i = 0; i <= N / Z; i++) {
    deque<int>& q = ::q[i];
    while (q.size() > 1) {
      int a = q.front();
      q.pop_front();
      int b = q.front();
      if (val[a] + a * 1LL * freq[i] < val[b] + b * 1LL * freq[i]) continue;
      q.push_front(a);
      break;
    }
    if (val[ret] + freq[ret / Z] * 1LL * ret <
        val[q.front()] + q.front() * 1LL * freq[i])
      ret = q.front();
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &w);
  ans = n;
  for (int i = 0, a, b; i < n; i++) {
    scanf("%d%d", &a, &b);
    v[b + 1].push_back(a);
    mx = max(mx, b + 1);
  }
  for (int i = 0; i <= N / Z; i++) build(i);
  for (int i = 0; i <= mx; i++) {
    for (auto j : v[i]) {
      ans--;
      int to = j / Z;
      for (int i = 0; i < to; i++) freq[i]++;
      for (int i = to * Z; i <= j; i++) val[i] += i;
      bad = 1;
      build(to);
    }
    int temp = get();
    printf("%lld %d\n",
           ans * 1LL * i * w + val[temp] + temp * 1LL * freq[temp / Z], temp);
  }
}