B - 花壇の配置図 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は広大な植物園の管理者です。植物園には N 個の花壇があり、それぞれの花壇は平面上の互いに異なる位置に設置されています。花壇 i（1 \leq i \leq N）の座標は (X_i, Y_i) です。

なお、異なる花壇が同じ X 座標を持つことや、同じ Y 座標を持つことはありえます。

高橋君は、すべての花壇の位置をまとめた配置図を作成することにしました。配置図は以下のように定義されるグリッドです。

N 個の花壇の X 座標のうち相異なる値の個数を C_x、Y 座標のうち相異なる値の個数を C_y とします。X 座標の相異なる値を小さい順に x_1 < x_2 < \cdots < x_{C_x}、Y 座標の相異なる値を小さい順に y_1 < y_2 < \cdots < y_{C_y} とします。

配置図は C_x \times C_y 個のセルからなるグリッドです。各セルはインデックスの組 (p, q)（1 \leq p \leq C_x, 1 \leq q \leq C_y）に一対一に対応し、セル (p, q) は座標 (x_p, y_q) を表します。

各花壇 i の座標 (X_i, Y_i) について、X_i = x_p, Y_i = y_q を満たす p, q がそれぞれちょうど1つ存在するので、花壇 i はセル (p, q) に配置されます。花壇の座標は互いに異なるため、各花壇は異なるセルに配置され、花壇が配置されているセルの数はちょうど N 個です。

配置図の 空きセル数 を、セルの総数から花壇の数を引いた値、すなわち C_x \times C_y - N と定義します。

ここで、青木君（高橋君の同僚）は、高橋君に追加の課題を出しました。N 個の花壇から 1 つを選んで取り除いたとき、残りの N - 1 個の花壇で同様に配置図を作成した場合の空きセル数を、取り除く花壇ごとにそれぞれ求めよ、というものです。

すなわち、各 i = 1, 2, \ldots, N について、花壇 i を除いた残りの N - 1 個の花壇に対して上記の手順で配置図を作成してください。残りの N - 1 個の花壇の X 座標のうち相異なる値の個数を C'_x、Y 座標のうち相異なる値の個数を C'_y とすると、空きセル数は C'_x \times C'_y - (N - 1) です。この値を各 i について求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • -10^9 \leq Y_i \leq 10^9
  • (X_i, Y_i) \neq (X_j, Y_j) （i \neq j）
  • 入力はすべて整数である

入力

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • 1 行目には、花壇の個数を表す整数 N が与えられる。
  • 2 行目から N + 1 行目では、各花壇の座標が与えられる。
  • 1 + i 行目には、花壇 i の X 座標 X_i と Y 座標 Y_i が、スペース区切りで与えられる。

出力

N 行出力せよ。i 行目には、花壇 i を除外した場合の空きセル数を出力せよ。

入力例 1

4
1 1
1 2
2 1
3 3

出力例 1

6
3
3
1

入力例 2

3
0 0
1 1
2 2

出力例 2

2
2
2

入力例 3

10
1 3
1 5
2 3
2 7
3 1
3 5
4 1
4 7
5 3
5 5

出力例 3

11
11
11
11
11
11
11
11
11
11

入力例 4

20
-10 4
-10 7
-5 2
-5 4
-5 9
0 1
0 4
0 7
0 9
3 2
3 7
3 9
6 1
6 2
6 4
8 1
8 7
8 9
10 2
10 4

出力例 4

16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16

入力例 5

2
1000000000 -1000000000
-1000000000 1000000000

出力例 5

0
0

Score : 333 pts

Problem Statement

Takahashi is the manager of a vast botanical garden. The garden has N flower beds, each placed at a distinct position on a plane. The coordinates of flower bed i (1 \leq i \leq N) are (X_i, Y_i).

Note that different flower beds may share the same X coordinate or the same Y coordinate.

Takahashi has decided to create a layout map summarizing the positions of all flower beds. The layout map is a grid defined as follows.

Let C_x be the number of distinct values among the X coordinates of the N flower beds, and C_y be the number of distinct values among the Y coordinates. Let the distinct X coordinate values in ascending order be x_1 < x_2 < \cdots < x_{C_x}, and the distinct Y coordinate values in ascending order be y_1 < y_2 < \cdots < y_{C_y}.

The layout map is a grid consisting of C_x \times C_y cells. Each cell corresponds one-to-one with an index pair (p, q) (1 \leq p \leq C_x, 1 \leq q \leq C_y), where cell (p, q) represents the coordinates (x_p, y_q).

For each flower bed i with coordinates (X_i, Y_i), there exists exactly one p and one q such that X_i = x_p and Y_i = y_q, so flower bed i is placed in cell (p, q). Since all flower bed coordinates are distinct, each flower bed is placed in a different cell, and the number of cells containing a flower bed is exactly N.

The number of empty cells in the layout map is defined as the total number of cells minus the number of flower beds, namely C_x \times C_y - N.

Now, Aoki (Takahashi's colleague) has given Takahashi an additional task: for each flower bed, determine the number of empty cells in the layout map created from the remaining N - 1 flower beds when that flower bed is removed.

Specifically, for each i = 1, 2, \ldots, N, create the layout map using the above procedure for the remaining N - 1 flower beds after removing flower bed i. Let C'_x be the number of distinct values among the X coordinates and C'_y be the number of distinct values among the Y coordinates of the remaining N - 1 flower beds. The number of empty cells is C'_x \times C'_y - (N - 1). Compute this value for each i.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • -10^9 \leq Y_i \leq 10^9
  • (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
  • All input values are integers

Input

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • The first line contains an integer N, the number of flower beds.
  • The 2nd through (N + 1)-th lines give the coordinates of each flower bed.
  • The (1 + i)-th line contains the X coordinate X_i and Y coordinate Y_i of flower bed i, separated by a space.

Output

Print N lines. The i-th line should contain the number of empty cells when flower bed i is removed.

Sample Input 1

4
1 1
1 2
2 1
3 3

Sample Output 1

6
3
3
1

Sample Input 2

3
0 0
1 1
2 2

Sample Output 2

2
2
2

Sample Input 3

10
1 3
1 5
2 3
2 7
3 1
3 5
4 1
4 7
5 3
5 5

Sample Output 3

11
11
11
11
11
11
11
11
11
11

Sample Input 4

20
-10 4
-10 7
-5 2
-5 4
-5 9
0 1
0 4
0 7
0 9
3 2
3 7
3 9
6 1
6 2
6 4
8 1
8 7
8 9
10 2
10 4

Sample Output 4

16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16

Sample Input 5

2
1000000000 -1000000000
-1000000000 1000000000

Sample Output 5

0
0