#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 9;
const int add = 2e6;
const int Max = 4e6 + 10;
int n, r, x, y, R = 0, ans;
struct Node {
    int x, y;
} points[N];
bool cmp (Node x, Node y) {
    return x.x < y.x;
}
deque <int> d;

class SegmentTree {
public:
    SegmentTree(int n) : n(n) {
        data.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    int query() {
        return data[1];
    }

private:
    int n;
    vector<int> data;
    vector<int> lazy;

    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            data[node] += lazy[node];
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void update(int node, int start, int end, int l, int r, int x) {
        push(node, start, end);
        if (r < start || l > end) return;
        if (l <= start && end <= r) {
            data[node] += x;
            if (start != end) {
                lazy[2 * node] += x;
                lazy[2 * node + 1] += x;
            }
            return;
        }
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, x);
        update(2 * node + 1, mid + 1, end, l, r, x);
        data[node] = max(data[2 * node], data[2 * node + 1]);
    }
} tree(Max);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> r;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        points[i] = {x - y + add, x + y + add};
    }
    sort(points + 1, points + n + 1, cmp);
    
    for (int i = 0; i <= Max; i++) {
        while (R + 1 <= n && points[R + 1].x <= i + r) {
            d.push_back(R + 1);
            R++;
            tree.update(points[R].x - r, points[R].x + r, 1);
        }
        while (points[d.front()].x < i - r) {
            tree.update(points[d.front()].x - r, points[d.front()].x + r, -1);
            d.pop_front();
        }
        ans = max(ans, tree.query());
        cout << i << '\n';
    }
    cout << ans << '\n';
    return 0;
}