白雪女王告诉凯用冰块组成一个词“永恒”。凯急于完成这项任务,因为这样他就会获得自由,雪之女王会给他全世界和一双溜冰鞋。
冰雪女王的宫殿后面有一个由细胞组成的无限领域。场地上分布着 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