Mưa sao băng

Một trận mưa sao băng đổ xuống một bãi đất được chia thành lưới ô vuông. Có \(N\) viên sao băng, viên thứ \(i\) rơi vào ô có tọa độ \((x_i, y_i)\) (nhiều viên có thể rơi vào cùng một ô).

Với số nguyên \(K\) cho trước, xét mọi hình vuông gồm \(K \times K\) ô liên tiếp của lưới (đặt ở mọi vị trí nguyên có thể). Với mỗi \(u = 1, 2, \dots, N\), hãy đếm có bao nhiêu hình vuông chứa đúng \(u\) viên sao băng. Hai hình vuông khác nhau nếu vị trí khác nhau.

Cụ thể, hình vuông có ô góc dưới trái là \((a, b)\) gồm các ô \((p, q)\) với \(a \le p \le a + K - 1\) và \(b \le q \le b + K - 1\).

Input

• Dòng đầu: hai số nguyên \(N\) và \(K\).
• \(N\) dòng tiếp theo: dòng thứ \(i\) gồm hai số nguyên \(x_i, y_i\).

Output

In ra \(N\) số nguyên trên một dòng, số thứ \(u\) là số hình vuông \(K \times K\) chứa đúng \(u\) viên sao băng.

Constraints

• \(1 \le N \le 10^5\), \(1 \le K \le 300\)
• \(-10^9 \le x_i, y_i \le 10^9\)
• Subtask 1 (40%): \(N \le 100\), \(K \le 5\), \(K \le x_i, y_i \le 100\)
• Subtask 2 (20%): \(N \le 1000\), \(K \le 50\), \(K \le x_i, y_i \le 1000\)
• Subtask 3 (20%): \(y_i = 2023\)
• Subtask 4 (20%): không có ràng buộc thêm

Sample Input

4 3
5 5
6 5
6 6
7 6

Sample Output

8 4 4 2

Explanation

Có \(8\) hình vuông \(3 \times 3\) chứa đúng \(1\) viên, \(4\) hình chứa đúng \(2\) viên, \(4\) hình chứa đúng \(3\) viên và \(2\) hình chứa cả \(4\) viên.