No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Extending Set of Points

time limit per test

3.5 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputFor a given set of two-dimensional points $$$S$$$, let's denote its extension $$$E(S)$$$ as the result of the following algorithm:

Create another set of two-dimensional points $$$R$$$, which is initially equal to $$$S$$$. Then, while there exist four numbers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ such that $$$(x_1, y_1) \in R$$$, $$$(x_1, y_2) \in R$$$, $$$(x_2, y_1) \in R$$$ and $$$(x_2, y_2) \notin R$$$, add $$$(x_2, y_2)$$$ to $$$R$$$. When it is impossible to find such four integers, let $$$R$$$ be the result of the algorithm.

Now for the problem itself. You are given a set of two-dimensional points $$$S$$$, which is initially empty. You have to process two types of queries: add some point to $$$S$$$, or remove some point from it. After each query you have to compute the size of $$$E(S)$$$.

Input

The first line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, each containing two integers $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le 3 \cdot 10^5$$$), denoting $$$i$$$-th query as follows: if $$$(x_i, y_i) \in S$$$, erase it from $$$S$$$, otherwise insert $$$(x_i, y_i)$$$ into $$$S$$$.

Output

Print $$$q$$$ integers. $$$i$$$-th integer should be equal to the size of $$$E(S)$$$ after processing first $$$i$$$ queries.

Example

Input

7 1 1 1 2 2 1 2 2 1 2 1 3 2 1

Output

1 2 4 4 4 6 3

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/27/2021 11:56:04 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|