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:
//package com.company;
// Always comment out package when submitting.

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {

        public class DisjointUnionWithUndo { // undo last operation
            public class Operation {
                int linkFrom, linkTo;
                int linkFromDepth, linkToDepth; // linkFromDepth <= linkToDepth
                int fromCountX, fromCountY; // result

                public Operation(int linkFrom, int linkTo, int linkFromDepth, int linkToDepth) {
                    this.linkFrom = linkFrom;
                    this.linkTo = linkTo;
                    this.linkFromDepth = linkFromDepth;
                    this.linkToDepth = linkToDepth;
                }
            }
            public class Result { // should be able to dynamically return the result upon connectivity changes;
                int[] componentCountX;
                int[] componentCountY;
                long ret; // for each component x * y;
                int countEdges;
                public Result(int a, int b) {
                    componentCountX = new int[n];
                    componentCountY = new int[n];
                    for (int i = 0; i < a; i++) {
                        componentCountX[i] = 1;
                    }
                    for (int i = a; i < n; i++) {
                        componentCountY[i] = 1;
                    }
//                    for (int i = 0; i < n; i++) {
//                        ret += componentCountX[i] * componentCountY[i]; // 0
//                    }
                }

                public void connect(Operation op) { // update operation
                    int from = op.linkFrom;
                    int to = op.linkTo;
                    op.fromCountX = componentCountX[from];
                    op.fromCountY = componentCountY[from];
                    ret -= (long) componentCountX[from] * componentCountY[from];
                    ret -= (long) componentCountX[to] * componentCountY[to];
                    componentCountX[to] += componentCountX[from];
                    componentCountY[to] += componentCountY[from];
                    ret += (long) componentCountX[to] * componentCountY[to];
//                    countEdges++;
                }

                public void undo(Operation op) {
                    int from = op.linkFrom;
                    int to = op.linkTo;
                    ret -= (long) componentCountX[to] * componentCountY[to];
                    componentCountX[from] = op.fromCountX;
                    componentCountY[from] = op.fromCountY;
                    componentCountX[to] -= componentCountX[from];
                    componentCountY[to] -= componentCountY[from];
                    ret += (long) componentCountX[from] * componentCountY[from];
                    ret += (long) componentCountX[to] * componentCountY[to];
//                    countEdges--;
                }
            }
            int n;
            int[] parentArray; // -x, x = rank.
            Result result;
            List<Operation> operations;

            public DisjointUnionWithUndo(int n, int a) {
                this.n = n;
                parentArray = new int[n];
                Arrays.fill(parentArray, -1);
                operations = new ArrayList<>();
                result = new Result(a, n - a);
            }
            public int find(int v) { // no path compression to support undos
                while (parentArray[v] >= 0){
                    v = parentArray[v];
                }
                return v;
            }
            public void union(int u, int v) {
                int ru = find(u), rv = find(v);
                if (ru == rv) return;
                if (parentArray[ru] < parentArray[rv]) { // ru should be shallow
                    int t = ru; ru = rv; rv = t;
                }
                Operation op = new Operation(ru, rv, parentArray[ru], parentArray[rv]);
                parentArray[rv] = Math.min(parentArray[ru] - 1, parentArray[rv]);
                parentArray[ru] = rv;
                result.connect(op);
                operations.add(op);
            }
            public void undo() {
                Operation op = operations.get(operations.size() - 1);
                parentArray[op.linkTo] = op.linkToDepth;
                parentArray[op.linkFrom] = op.linkFromDepth;
                result.undo(op);
                operations.remove(operations.size() - 1);
            }
            public long getResult() {
                return result.ret - result.countEdges;
            }
        }

        public class DynamicConnectivity {
            public class EdgeExist {
                int u, v;
                int start, end;

                public EdgeExist(int u, int v, int start, int end) {
                    this.u = u;
                    this.v = v;
                    this.start = start;
                    this.end = end;
                }
            }

            public long hashUV(int u, int v) { // u < v
                return u * (1L << 32) + v;
            }
            public int getU(long hashV) {
                return (int) (hashV / (1L << 32));
            }
            public int getV(long hashV) {
                return (int) (hashV % (1L << 32));
            }

            int n; // vertices
            int q; // queries == time
            int curTime;
            long[] resultAtTimeStep;
            Map<Long, Integer> edgeQueryMap;
            EdgeExist[] edgeExists;
            DisjointUnionWithUndo djs;
            public DynamicConnectivity(int n, int q, int a) {
                edgeQueryMap = new HashMap<>();
                edgeExists = new EdgeExist[q];
                curTime = 0;
                this.n = n;
                this.q = q;
                djs = new DisjointUnionWithUndo(n, a);
                resultAtTimeStep = new long[q + 1];
                resultAtTimeStep[0] = djs.result.ret - djs.getResult();
            }

            public void tweakEdge(int u, int v) {
                if (u > v) tweakEdge(v, u);
                long hashVal = hashUV(u, v);
                if (edgeQueryMap.containsKey(hashVal)) {
                    int start = edgeQueryMap.get(hashVal);
                    EdgeExist edge = new EdgeExist(u, v, start, curTime);
                    edgeExists[start] = edge;
                    edgeExists[curTime] = edge;
                    edgeQueryMap.remove(hashVal);
                } else {
                    edgeQueryMap.put(hashVal, curTime);
                }
                curTime++;
            }

            public void computeForEveryTimeStep() {
                for (Map.Entry<Long, Integer> en: edgeQueryMap.entrySet()) {
                    int u = getU(en.getKey());
                    int v = getV(en.getKey());
                    edgeExists[en.getValue()] = new EdgeExist(u, v, en.getValue(), q);
                }
                go(0, q);
            }

            public void go(int timeStart, int timeEnd) {
                if (timeStart == timeEnd - 1) {
                    if (edgeExists[timeStart].end >= timeEnd) djs.union(edgeExists[timeStart].u, edgeExists[timeStart].v);
                    resultAtTimeStep[timeStart + 1] = djs.getResult();
                    return;
                }
                int size = djs.operations.size();
                int mid = (timeStart + timeEnd) / 2;
                for (int i = mid; i < timeEnd; i++) {
                    if (edgeExists[i].start <= timeStart) {
                        djs.union(edgeExists[i].u, edgeExists[i].v);
                    }
                }
                go(timeStart, mid);
                while (djs.operations.size() > size) {
                    djs.undo();
                }
                for (int i = timeStart; i < mid; i++) {
                    if (edgeExists[i].end >= timeEnd) {
                        djs.union(edgeExists[i].u, edgeExists[i].v);
                    }
                }
                go(mid, timeEnd);
                while (djs.operations.size() > size) {
                    djs.undo();
                }
            }

        }


        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int q = sc.nextInt();
            int[][] points = new int[q][2];
            Map<Integer, Integer> xCoordToXIdx = new HashMap<>();
            Map<Integer, Integer> yCoordToYIdx = new HashMap<>();
            for (int i = 0; i < q; i++) {
                {
                    int x = sc.nextInt();
                    if (!xCoordToXIdx.containsKey(x)) {
                        xCoordToXIdx.put(x, xCoordToXIdx.size());
                    }
                    x = xCoordToXIdx.get(x);
                    points[i][0] = x;
                }
                {
                    int y = sc.nextInt();
                    if (!yCoordToYIdx.containsKey(y)) {
                        yCoordToYIdx.put(y, yCoordToYIdx.size());
                    }
                    y = yCoordToYIdx.get(y);
                    points[i][1] = y;
                }
            }
            int a = xCoordToXIdx.size();
            DynamicConnectivity dc = new DynamicConnectivity(a + yCoordToYIdx.size(), q, a);
            for (int[] edge: points) {
                dc.tweakEdge(edge[0], edge[1] + a);
            }
            dc.computeForEveryTimeStep();
            for (int i = 1; i <= q; i++) {
                pw.print(dc.resultAtTimeStep[i] + " ");
            }
        }
    }

    // template, actual code is in class Task.
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("balance.out"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}