F. Extending Set of Pointstime limit per test3.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard 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).InputThe 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.OutputPrint q integers. i-th integer should be equal to the size of E(S) after processing first i queries.ExampleInput
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
Output
1 2 4 4 4 6 3 
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1

1 2 4 4 4 6 3 
['data structures', 'divide and conquer', 'dsu', '*2600']