問題文

二次元平面上に 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
• 入力は全て整数

入力例 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