Problem: Snow Queen told Kay to form a word "eternity" using pieces of ice. Kay is eager to deal with the task, because he will then become free, and Snow Queen will give him all the world and a pair of skates.

Behind the palace of the Snow Queen there is an infinite field consisting of cells. There are n pieces of ice spread over the field, each piece occupying exactly one cell and no two pieces occupying the same cell. To estimate the difficulty of the task Kay looks at some squares of size k × k cells, with corners located at the corners of the cells and sides parallel to coordinate axis and counts the number of pieces of the ice inside them.

This method gives an estimation of the difficulty of some part of the field. However, Kay also wants to estimate the total difficulty, so he came up with the following criteria: for each x (1 ≤ x ≤ n) he wants to count the number of squares of size k × k, such that there are exactly x pieces of the ice inside.

Please, help Kay estimate the difficulty of the task given by the Snow Queen.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 300) — the number of pieces of the ice and the value k, respectively. Each of the next n lines contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — coordinates of the cell containing i-th piece of the ice. It's guaranteed, that no two pieces of the ice occupy the same cell.

Output

Print n integers: the number of squares of size k × k containing exactly 1, 2, ..., n pieces of the ice.

Example

Input

5 3
4 5
4 6
5 5
5 6
7 7


Output

10 8 1 4 0 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Iterator;
import java.io.IOException;
import java.util.Random;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;
import java.util.function.IntFunction;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DKayAndEternity solver = new DKayAndEternity();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DKayAndEternity {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int k = in.readInt();
            Cell[] cells = new Cell[n];
            long[] cnts = new long[n + 1];
            long[] ans = new long[n + 1];

            int inf = (int) 1e9 + 500;
            IntegerArrayList xs = new IntegerArrayList(n + 2);
            xs.add(-inf);
            xs.add(inf);
            IntegerArrayList ys = new IntegerArrayList(n);
            for (int i = 0; i < n; i++) {
                cells[i] = new Cell();
                cells[i].x = in.readInt();
                cells[i].y = in.readInt();
                xs.add(cells[i].x);
                ys.add(cells[i].y);
            }

            Arrays.sort(cells, (a, b) -> Integer.compare(a.y, b.y));
            IntegerDiscreteMap xsDM = new IntegerDiscreteMap(xs.getData(), 0, xs.size());
            int[] xVal = new int[xsDM.maxRank() + 1];
            for (int i = 0; i <= xsDM.maxRank(); i++) {
                xVal[i] = xsDM.iThElement(i);
            }

            int size = 0;
            int[] row = new int[xsDM.maxRank() + 1];
            SimplifiedDeque<Cell> addDq = new Range2DequeAdapter<>(i -> cells[i], 0, cells.length - 1);
            SimplifiedDeque<Cell> removeDq = new Range2DequeAdapter<>(i -> cells[i], 0, cells.length - 1);
            for (int i = -inf; i < inf; i++) {
                while (!removeDq.isEmpty() && removeDq.peekFirst().y < i) {
                    Cell head = removeDq.removeFirst();
                    int xRank = xsDM.rankOf(head.x);
                    int l = xRank;
                    int r = xRank;
                    int cur = row[xRank];

                    while (xVal[r] - xVal[l - 1] + 1 <= k) {
                        cur += row[l - 1];
                        l--;
                    }
                    for (int j = xVal[xRank] - k + 1; j <= xVal[xRank]; j++) {
                        while (xVal[r + 1] - j + 1 <= k) {
                            r++;
                            cur += row[r];
                        }
                        while (xVal[l] < j) {
                            cur -= row[l];
                            l++;
                        }
                        cnts[cur]--;
                        if (cur > 0) {
                            cnts[cur - 1]++;
                        }
                    }

                    row[xRank]--;
                    size--;
                }
                while (!addDq.isEmpty() && addDq.peekFirst().y < i + k) {
                    Cell head = addDq.removeFirst();
                    int xRank = xsDM.rankOf(head.x);
                    int l = xRank;
                    int r = xRank;
                    int cur = row[xRank];

                    while (xVal[r] - xVal[l - 1] + 1 <= k) {
                        cur += row[l - 1];
                        l--;
                    }
                    for (int j = xVal[xRank] - k + 1; j <= xVal[xRank]; j++) {
                        while (xVal[r + 1] - j + 1 <= k) {
                            r++;
                            cur += row[r];
                        }
                        while (xVal[l] < j) {
                            cur -= row[l];
                            l++;
                        }
                        cnts[cur]--;
                        cnts[cur + 1]++;
                    }

                    row[xRank]++;
                    size++;
                }


                if (size == 0) {
                    int next = inf;
                    if (!addDq.isEmpty()) {
                        next = addDq.peekFirst().y - k + 1;
                    }
                    i = next - 1;
                    continue;
                }

                for (int j = 1; j <= size; j++) {
                    ans[j] += cnts[j];
                }
            }

            for (int i = 1; i <= n; i++) {
                out.println(ans[i]);
            }
        }

    }

    static class IntegerArrayList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public int[] getData() {
            return data;
        }

        public IntegerArrayList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerArrayList(IntegerArrayList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerArrayList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerArrayList list) {
            addAll(list.data, 0, list.size);
        }

        public int size() {
            return size;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

        public String toString() {
            return Arrays.toString(toArray());
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerArrayList)) {
                return false;
            }
            IntegerArrayList other = (IntegerArrayList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerArrayList clone() {
            IntegerArrayList ans = new IntegerArrayList();
            ans.addAll(this);
            return ans;
        }

    }

    static class SequenceUtils {
        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static interface SimplifiedStack<T> extends Iterable<T> {
        boolean isEmpty();

    }

    static class RandomWrapper {
        private Random random;
        public static final RandomWrapper INSTANCE = new RandomWrapper(new Random());

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }

    }

    static class IntegerDiscreteMap {
        int[] val;
        int f;
        int t;

        public IntegerDiscreteMap(int[] val, int f, int t) {
            Randomized.shuffle(val, f, t);
            Arrays.sort(val, f, t);
            int wpos = f + 1;
            for (int i = f + 1; i < t; i++) {
                if (val[i] == val[i - 1]) {
                    continue;
                }
                val[wpos++] = val[i];
            }
            this.val = val;
            this.f = f;
            this.t = wpos;
        }

        public int rankOf(int x) {
            return Arrays.binarySearch(val, f, t, x) - f;
        }

        public int iThElement(int i) {
            return val[f + i];
        }

        public int maxRank() {
            return t - f - 1;
        }

        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(val, f, t));
        }

    }

    static class Randomized {
        public static void shuffle(int[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                int tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static int nextInt(int l, int r) {
            return RandomWrapper.INSTANCE.nextInt(l, r);
        }

    }

    static class Cell {
        int x;
        int y;

        public String toString() {
            return String.format("(%d, %d)", x, y);
        }

    }

    static interface SimplifiedDeque<T> extends SimplifiedStack<T> {
        T peekFirst();

        T removeFirst();

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class Range2DequeAdapter<T> implements SimplifiedDeque<T> {
        IntFunction<T> data;
        int l;
        int r;

        public Range2DequeAdapter(IntFunction<T> data, int l, int r) {
            this.data = data;
            this.l = l;
            this.r = r;
        }

        public boolean isEmpty() {
            return l > r;
        }

        public T peekFirst() {
            return data.apply(l);
        }

        public T removeFirst() {
            return data.apply(l++);
        }

        public Iterator<T> iterator() {
            return new Iterator<T>() {
                int iter = l;


                public boolean hasNext() {
                    return iter <= r;
                }


                public T next() {
                    return data.apply(iter++);
                }
            };
        }

    }
}