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.lang.*;
import java.math.*;
import java.util.*;
import java.io.*;

public class Main {
class Node {
    int x;
    int y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
    public boolean equals(Object o){
        Node c=(Node)o;
        return x==c.x && y==c.y;
    }
    public int hashCode(){
        return x+y;
    }
}
class Node2 {
    int v,u,szxv,szyv,szxu,szyu;
    public Node2(int v,int u,int szxv,int szyv,int szxu,int szyu){
        this.v=v;
        this.u=u;

        this.szxv=szxv;
        this.szyv=szyv;
        this.szxu=szxu;
        this.szyu=szyu;
    }
}
    void solve() {
        int q=ni();

        HashMap<Node,Integer> mp=new HashMap<>();
        tree=new ArrayList[4*q+1];
        for(int i=1;i<=4*q;i++) tree[i]=new ArrayList<>();
        for(int i=0;i<q;i++){
            int x=ni(),y=ni();

              if(!mp.containsKey(new Node(x,y))) {
                  mp.put(new Node(x, y), i + 1);
              }else {
                  int st = mp.get(new Node(x, y));
                  mp.remove(new Node(x, y));
                  update(1, st, i, 1, q, new Node(x, y));
                //  pw.println(x+" "+y+" "+st+" "+i);
              }

        }
        for(Map.Entry<Node,Integer> e : mp.entrySet()){
            Node p=e.getKey(); int st=e.getValue();
            update(1,st,q,1,q,new Node(p.x,p.y));
       //     pw.println(p.x+" "+p.y+" "+st+" "+q);
        }
        F=new int[2*MX+1];
        szx=new int[2*MX+1];
        szy=new int[2*MX+1];
        for(int i=1;i<=MX;i++){
            F[i]=i; F[i+MX]=i+MX;
            szx[i]=1; szy[i+MX]=1;
        }
        ans2=new long[q+1];
        go(1,1,q);
        for(int i=1;i<=q;i++) pw.print(ans2[i]+" ");
        pw.println("");



    }
    int MX=300000;
    ArrayList<Node> tree[];
    int F[];
    int szx[],szy[];
    long ans=0;
    long ans2[];
    boolean bl=false;
    Stack<Node2>stk=new Stack<>();
    void go(int id,int l,int r){
        long prevans=ans;

        for(Node p : tree[id]){
            merge(p.x,p.y);

        }
        if(l==r){
            ans2[l]=ans;
//            pw.println(l);

        }else {
            int mid=(l+r)>>1;
            go(2*id,l,mid);
            go(2*id+1,mid+1,r);
        }

        ans=prevans;
        int k=tree[id].size();
        while(k-->0){
            Node2 p=stk.pop();
            F[p.v]=p.v;
            F[p.u]=p.u;
            szx[p.v]=p.szxv;
            szy[p.v]=p.szyv;
            szx[p.u]=p.szxu;
            szy[p.u]=p.szyu;
           // pw.println(p.v+" "+p.u+"  rollback"+" "+szx[p.v]+" "+szy[p.v]+" "+szx[p.u]+" "+szy[p.u]);
        }

    }

    int root(int a){
        while(a!=F[a]){
            a=F[a];
        }
        return a;
    }
    void merge(int x,int y){
        int u=root(x),v=root(y+MX);
        stk.push(new Node2(v,u,szx[v],szy[v],szx[u],szy[u]));
      //  pw.println(v+" "+u+" "+x+" "+y+" "+szx[v]+" "+szy[v]+" "+szx[u]+" "+szy[u]);
        if(u==v){

            return;
        }
        ans-=(szx[u]*1L*szy[u]);
        ans-=(szx[v]*1L*szy[v]);
        if(szx[u]+szy[u]>szx[v]+szy[v]){
            int tmp=u; u=v; v=tmp;
        }

        szx[v]+=szx[u]; szy[v]+=szy[u];
        F[u]=v;
        ans+=(szx[v]*1L*szy[v]);

    }

    void update(int id,int x,int y,int l,int r,Node p){
        if(r<x || l>y) return;
        if(x==l && y==r) {
         //  pw.println(l+" "+r+" "+p.x+" "+p.y);
            tree[id].add(new Node(p.x,p.y));
            return;
        }
        int mid=(l+r)>>1;
        if(y<=mid) update(2*id,x,y,l,mid,p);
        else if(x>mid) update(2*id+1,x,y,mid+1,r,p);
        else {
            update(2*id,x,mid,l,mid,p);
            update(2*id+1,mid+1,y,mid+1,r,p);
        }
    }
    long M = (long)1e9+7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";

    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");

    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
    }

}