#P18351. Omniscient Artist

Omniscient Artist

Omniscient Artist

平面上有 nn 个边平行于坐标轴的矩形。第 ii 个矩形为半开区域

[x1,i,x2,i)×[y1,i,y2,i).[x_{1,i},x_{2,i})\times[y_{1,i},y_{2,i}).

给定正整数 mm,且 m≥nm\ge\sqrt n。请依次求出恰好被 m,2m,…,⌊n/m⌋mm,2m,\ldots,\lfloor n/m\rfloor m 个矩形覆盖的区域面积。

形式化地,对于整数坐标 (x,y)(x,y),令

$$C(x,y)=\sum_{i=1}^{n} [x_{1,i}\le x<x_{2,i}]\,[y_{1,i}\le y<y_{2,i}].$$

对每个 1≤c≤⌊n/m⌋1\le c\le\lfloor n/m\rfloor,求满足 C(x,y)=cmC(x,y)=cm 的整数点 (x,y)(x,y) 数量。由于矩形边界均为整数,这等于恰好被 cmcm 个矩形覆盖的单位格面积。

矩形可以重合,重合的矩形仍分别计入覆盖次数。只统计指定的恰好覆盖次数,不统计至少覆盖这些次数的面积。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行,每行四个整数,顺序为

x1,ix2,iy1,iy2,i.x_{1,i}\quad x_{2,i}\quad y_{1,i}\quad y_{2,i}.

数据范围:

  • 2≤n≤3×1052\le n\le3\times10^5;
  • mm 为整数,n≤m≤n\sqrt n\le m\le n;
  • 1≤x1,i<x2,i≤n1\le x_{1,i}<x_{2,i}\le n;
  • 1≤y1,i<y2,i≤n1\le y_{1,i}<y_{2,i}\le n。

输出格式

输出 ⌊n/m⌋\lfloor n/m\rfloor 行。

第 cc 行输出恰好被 cmcm 个矩形覆盖的区域面积。

样例输入 1

9 3
6 8 4 5
6 9 1 3
1 5 1 9
6 8 7 9
5 6 2 9
2 8 1 2
1 8 5 9
2 4 5 7
7 9 2 6

样例输出 1

4
0
0

样例输入 2

10 4
1 2 1 6
3 9 8 9
2 3 1 9
2 8 8 10
3 7 2 10
1 7 2 7
5 6 2 6
5 8 3 7
6 7 4 7
1 4 7 10

样例输出 2

7
0