028 - Cluttered Paper(★4) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4

問題文

二次元平面上に N 枚の長方形の紙があります。すべての紙は辺が x 軸または y 軸に平行に なるように配置されており、i 枚目の紙の左下角の座標は (lx_i, ly_i) 、右上角の座標は (rx_i, ry_i) です。 k=1,2,3, \dots, N について、次の値を求めてください。

  • 紙がちょうど k 枚重なっている部分の面積

制約

  • 1 \leq N \leq 10^5
  • 0 \leq lx_i \lt rx_i \leq 1000
  • 0 \leq ly_i \lt ry_i \leq 1000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N
lx_1 ly_1 rx_1 ry_1
lx_2 ly_2 rx_2 ry_2
\vdots
lx_N ly_N rx_N ry_N

出力

紙がちょうど k 枚重なっている部分の面積を A_k として、以下の形式で出力してください。

A_1
A_2
\vdots
A_N

入力例 1

2
1 1 3 2
2 1 4 2

出力例 1

2
1

紙が 1 枚重なっている部分の面積は 2、紙が 2 枚重なっている部分の面積は 1 です。


入力例 2

2
1 1 3 4
3 4 6 5

出力例 2

9
0

紙同士が重ならないことがあります。


入力例 3

20
61 98 76 100
70 99 95 100
10 64 96 91
12 37 99 66
63 93 65 95
16 18 18 67
30 47 88 56
33 6 38 8
37 19 40 68
4 56 12 84
3 16 92 78
39 24 67 96
46 1 69 57
40 34 65 65
20 38 51 92
5 32 100 73
7 33 92 55
4 46 97 85
43 18 57 87
15 29 54 74

出力例 3

1806
990
1013
1221
567
839
413
305
228
121
58
40
0
0
0
0
0
0
0
0

Source Name

「競プロ典型90問」28日目