← 返回题目列表

Codeforces · 685/D

D. 凯和永恒

中文机器翻译题面 查看原题

白雪女王告诉凯用冰块组成一个词“永恒”。凯急于完成这项任务,因为这样他就会获得自由,雪之女王会给他全世界和一双溜冰鞋。

冰雪女王的宫殿后面有一个由细胞组成的无限领域。场地上分布着 n 块冰,每块冰恰好占据一个单元格,并且没有两块冰块占据同一单元格。为了估计任务的难度,Kay 观察一些大小为 k × k 的方格,其角位于方格的角处,边平行于坐标轴,并计算其中冰块的数量。

该方法给出了该领域某些部分的难度估计。然而,Kay 也想估计总难度,因此他提出了以下标准:对于每个 x (1 ≤ x ≤ n),他想计算大小为 k × k 的方格的数量,使得里面正好有 x 块冰。

请帮凯估算一下冰雪女王交给的任务的难度。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 300)——分别是冰块的数量和 k 值。接下来的 n 行中的每一行都包含两个整数 xi 和 yi (- 109 ≤ xi, yi ≤ 109)——包含第 i 块冰的单元格的坐标。可以保证没有两块冰占据同一个单元。

输出

打印 n 个整数:大小为 k × k 的方格数,其中恰好包含 1, 2, ..., n 块冰。

示例

输入 #1

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

输出 #1

10 8 1 4 0