Problem: For 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) ∈ R, (x_1, y_2) ∈ R, (x_2, y_1) ∈ R and (x_2, y_2) ∉ 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 ≤ q ≤ 3 ⋅ 10^5) — the number of queries.

Then q lines follow, each containing two integers x_i, y_i (1 ≤ x_i, y_i ≤ 3 ⋅ 10^5), denoting i-th query as follows: if (x_i, y_i) ∈ 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 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class F {
    public static void main(String[] args) throws IOException {
        try (Input input = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            int n = input.nextInt();
            final class Coordinate {
                private final int axis, value;

                private Coordinate(int axis, int value) {
                    this.axis = axis;
                    this.value = value;
                }

                @Override
                public boolean equals(Object o) {
                    if (this == o) return true;
                    Coordinate that = (Coordinate) o;
                    return axis == that.axis &&
                            value == that.value;
                }

                @Override
                public int hashCode() {
                    return Objects.hash(axis, value);
                }
            }
            final class Point {
                private final int x, y;

                private Point(int x, int y) {
                    this.x = x;
                    this.y = y;
                }

                @Override
                public boolean equals(Object o) {
                    if (this == o) return true;
                    Point point = (Point) o;
                    return x == point.x &&
                            y == point.y;
                }

                @Override
                public int hashCode() {
                    return Objects.hash(x, y);
                }
            }
            Map<Coordinate, Integer> coordToIndex = new HashMap<>();
            final int MAX_COORDS = 600_000;
            int[] axis = new int[MAX_COORDS];
            Point[] points = new Point[n];
            for (int i = 0; i < n; i++) {
                int[] coords = new int[2];
                for (int j = 0; j < 2; j++) {
                    Coordinate c = new Coordinate(j, input.nextInt());
                    int index = coordToIndex.getOrDefault(c, coordToIndex.size());
                    if (index == coordToIndex.size()) {
                        coordToIndex.put(c, index);
                        axis[index] = j;
                    }
                    coords[j] = index;
                }
                points[i] = new Point(coords[0], coords[1]);
            }
            int totalCoords = coordToIndex.size();
            class DSU {
                private int[] roots = new int[totalCoords]; {
                    for (int i = 0; i < totalCoords; i++) {
                        roots[i] = i;
                    }
                }
                private int[] heights = new int[totalCoords]; {
                    for (int i = 0; i < totalCoords; i++) {
                        heights[i] = 1;
                    }
                }

                private int[] x = new int[totalCoords];
                private int[] y = new int[totalCoords]; {
                    for (int i = 0; i < totalCoords; i++) {
                        x[i] = 1 - axis[i];
                        y[i] = axis[i];
                    }
                }
                private long extensionSize = 0;

                private int findRoot(int x) {
                    return x == roots[x] ? x : findRoot(roots[x]);
                }

                private int[] operations = new int[n];
                private boolean[] increasedHeight = new boolean[n];
                private int operationCount = 0;

                boolean unite(int a, int b) {
                    a = findRoot(a);
                    b = findRoot(b);
                    if (a == b) {
                        return false;
                    }
                    if (heights[a] > heights[b]) {
                        int t = a;
                        a = b;
                        b = t;
                    }
                    if (heights[a] == heights[b]) {
                        increasedHeight[operationCount] = true;
                        heights[b]++;
                    } else {
                        increasedHeight[operationCount] = false;
                    }
                    operations[operationCount++] = a;
                    extensionSize -= (long)x[a] * y[a] + (long)x[b] * y[b];
                    roots[a] = b;
                    x[b] += x[a];
                    y[b] += y[a];
                    extensionSize += (long)x[b] * y[b];
                    return true;
                }

                void undoLastUnion() {
                    int a = operations[--operationCount];
                    int b = roots[a];
                    if (increasedHeight[operationCount]) {
                        heights[b]--;
                    }
                    extensionSize -= (long)x[b] * y[b];
                    x[b] -= x[a];
                    y[b] -= y[a];
                    roots[a] = a;
                    extensionSize += (long)x[a] * y[a] + (long)x[b] * y[b];
                }
            }
            class SegmentTree {
                int size = 1; {
                    while (size <= n) {
                        size *= 2;
                    }
                }

                private List[] p = new List[2 * size]; {
                    for (int i = 0; i < p.length; i++) {
                        p[i] = new ArrayList<Point>();
                    }
                }

                private void add(int l, int r, Point point) {
                    for (l += size, r += size; l < r; l /= 2, r /= 2) {
                        if (l % 2 == 1) {
                            p[l++].add(point);
                        }
                        if (r % 2 == 1) {
                            p[--r].add(point);
                        }
                    }
                }

                private void findExtensionSizes(int node, DSU dsu) {
                    int newUnions = 0;
                    for (Object o : p[node]) {
                        Point point = (Point)o;
                        if (dsu.unite(point.x, point.y)) {
                            newUnions++;
                        }
                    }
                    if (node >= size) {
                        if (node - size < n) {
                            writer.print(dsu.extensionSize + " ");
                        }
                    } else {
                        findExtensionSizes(2 * node, dsu);
                        findExtensionSizes(2 * node + 1, dsu);
                    }
                    for (int i = 0; i < newUnions; i++) {
                        dsu.undoLastUnion();
                    }
                }

                private void findExtensionSizes() {
                    findExtensionSizes(1, new DSU());
                }
            }
            SegmentTree segmentTree = new SegmentTree();
            Map<Point, Integer> pointSet = new HashMap<>();
            for (int i = 0; i < n; i++) {
                if (pointSet.containsKey(points[i])) {
                    segmentTree.add(pointSet.get(points[i]), i, points[i]);
                    pointSet.remove(points[i]);
                } else {
                    pointSet.put(points[i], i);
                }
            }
            for (Map.Entry<Point, Integer> entry : pointSet.entrySet()) {
                segmentTree.add(entry.getValue(), n, entry.getKey());
            }
            segmentTree.findExtensionSizes();
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

        default int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        default long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}