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:
// Don't place your source in a package
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;


// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {//scanner from SecondThread
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(System.out);



        int T=1;
        for(int t=0;t<T;t++){
            int n=Int();
            int A[][]=new int[n][2];
            for(int i=0;i<n;i++){
                A[i][0]=Int();
                A[i][1]=Int();
            }


            Solution sol=new Solution();
            sol.solution(out,A);
        }
        out.flush();

    }

    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}



class Solution{
    long res[];
    int nx[]=new int[300050*2];
    int ny[]=new int[300050*2];
    long cnt=0;
    int nums[]=new int[300050*2];
    int rank[]=new int[300050*2];

    public void solution(PrintWriter out,int A[][]){
        //offline processing
        int n=A.length;
        res=new long[n];
        Seg seg=new Seg(0,n-1);

        for(int i=0;i<nums.length;i++){
            nums[i]=i;
            rank[i]=1;
        }

        //important
        for(int i=0;i<300001;i++){
            nx[i]=1;
        }
        for(int j=300005;j<ny.length;j++){
            ny[j]=1;
        }

        Map<String,List<Integer>>f=new HashMap<>();
        for(int i=0;i<A.length;i++){
            String state=A[i][0]+","+A[i][1];
            if(!f.containsKey(state))f.put(state,new ArrayList<>());
            f.get(state).add(i);
        }


        for(String key:f.keySet()){
            String p[]=key.split(",");
            int x=Integer.parseInt(p[0]),y=Integer.parseInt(p[1]);
            List<Integer>list=f.get(key);
            for(int i=0;i<list.size();i+=2){//taking effect from [l,r-1]
                int l=list.get(i);
                int r=n-1;
                if(i+1<list.size()){
                    r=list.get(i+1)-1;
                }
                seg.add(l,r,new int[]{x,y+300005});
            }
        }

        dfs(seg);

        for(long i:res){
            out.print(i+" ");
        }
    }

    public void dfs(Seg root){
        List<int[]>query=root.query;
        Stack<int[]>sta=new Stack<>();
        long oldcnt=cnt;
        for(int q[]:query){
            int x=q[0],y=q[1];
            int r1=find(nums,x);
            int r2=find(nums,y);
            if(r1!=r2){
                cnt-=((nx[r1]+0l)*ny[r1]);
                cnt-=((nx[r2]+0l)*ny[r2]);

                if(rank[r1]>rank[r2]){
                    rank[r1]+=rank[r2];
                    nx[r1]+=nx[r2];
                    ny[r1]+=ny[r2];
                    nums[r2]=r1;
                    cnt+=((nx[r1]+0l)*ny[r1]);
                    sta.push(new int[]{r1,r2,0});
                }
                else{
                    rank[r2]+=rank[r1];
                    nx[r2]+=nx[r1];
                    ny[r2]+=ny[r1];
                    nums[r1]=r2;
                    cnt+=((nx[r2]+0l)*ny[r2]);
                    sta.push(new int[]{r1,r2,1});
                }

            }
        }


        //leaf
        if(root.left==null&&root.right==null){
            res[root.l]=cnt;
        }
        else{
            dfs(root.left);
            dfs(root.right);
        }

        //roll back
        while(sta.size()>0){
            int p[]=sta.pop();
            int r1=p[0],r2=p[1],state=p[2];
            if(state==0){
                nx[r1]-=nx[r2];
                ny[r1]-=ny[r2];
                rank[r1]-=rank[r2];
                nums[r2]=r2;

            }
            else{
                nx[r2]-=nx[r1];
                ny[r2]-=ny[r1];
                rank[r2]-=rank[r1];
                nums[r1]=r1;
            }

        }
        cnt=oldcnt;

    }

    public int find(int nums[],int x){
        if(nums[x]==x)return x;
        int root=find(nums,nums[x]);
        return root;
    }

    class Seg{//segment tree
        int l,r;
        Seg left=null,right=null;
        List<int[]>query=new ArrayList<>();
        public Seg(int l,int r){
            this.l=l;
            this.r=r;
            if(l!=r){
                int mid=l+(r-l)/2;
                if(l<=mid)left=new Seg(l,mid);
                if(r>=mid+1)right=new Seg(mid+1,r);
            }else{

            }
        }

        public void add(int s,int e,int p[]){
            if(l==s&&r==e){//add the query to cur
                query.add(new int[]{p[0],p[1],0});
                return ;
            }
            int mid=l+(r-l)/2; //left :  to mid-1,
            if(e<=mid){
                left.add(s,e,p);
            }
            else if(s>=mid+1){
                right.add(s,e,p);
            }
            else{
                left.add(s,mid,p);
                right.add(mid+1,e,p);
            }
        }


    }

}