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.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    TreeSet<Point>[] tr;
    int[] set;
    long[] szx, szy;
    void solve(int TC) throws Exception{
        int n = ni();
        int[][] p = new int[n][];int c = 0;
        TreeMap<Point, Integer> map = new TreeMap<>();
        for(int i = 0; i< n; i++){
            Point pt = new Point(ni(), ni());
            if(map.containsKey(pt)){
                p[map.get(pt)][3] = i-1;
                map.remove(pt);
            }else{
                map.put(pt, c);
                p[c++] = new int[]{pt.x,pt.y, i, n-1};
            }
        }
        set = new int[2*MX];szx = new long[2*MX];szy = new long[2*MX];
        for(int i = 0; i< set.length; i++){
            set[i] = i;
            szx[i] = (i< MX?1:0);
            szy[i] = 1-szx[i];
        }
        tr = new TreeSet[4*n];
        for(int i = 0; i< tr.length; i++)tr[i] = new TreeSet<>();
        for(int i = 0; i< c; i++)add(p[i][2], p[i][3], 0, n-1, 1, new Point(p[i][0], p[i][1]));
        solve(1, 0, n-1);
    }
    void add(int l, int r, int ll, int rr, int i, Point p){
        if(l==ll && r==rr){
            tr[i].add(p);
            return;
        }
        int mid = (ll+rr)/2;
        if(r<=mid)add(l, r, ll, mid, i<<1, p);
        else if(l>mid)add(l,r,mid+1,rr,i<<1|1,p);
        else{
            add(l,mid,ll,mid,i<<1,p);
            add(mid+1,r,mid+1,rr,i<<1|1,p);
        }
    }
    int find(int[] set, int x){
        return set[x]==x?x:find(set, set[x]);
    }
    long ans = 0;
    void union(int[] set, long[] szx, long[] szy, int x, int y, Stack<Integer> s){
        x = find(set, x);y = find(set, y);
        if(x==y)return;
        if(szx[x]+szy[x]<szx[y]+szy[y]){
            int t = x;x = y;y = t;
        }
        set[y] = x;
        ans += szx[x]*szy[y]+szx[y]*szy[x];
        szx[x] += szx[y];
        szy[x] += szy[y];
        s.push(y);
    }
    void undo(Stack<Integer> s){
        while(!s.isEmpty()){
            int y = s.pop(), x = set[y];
            szx[x] -= szx[y];
            szy[x] -= szy[y];
            ans -= szx[x]*szy[y]+szx[y]*szy[x];
            set[y] = y;
        }
    }
    void solve(int i, int l, int r){
//        pni(i+" "+l+" "+r);
        Stack<Integer> s = new Stack<>();
        long aa = ans;
        for(Point p:tr[i])
            union(set, szx, szy, p.x, p.y+MX,s);
        int mid = (l+r)/2;
        if(l==r)p(ans+" ");
        else{
            solve(i<<1, l, mid);
            solve(i<<1|1, mid+1,r);
        }
        undo(s);ans = aa;
    }
    class Point implements Comparable<Point>{
        int x, y;
        public Point(int x, int y){
            this.x= x;this.y = y;
        }
        public int compareTo(Point p){
            if(x!=p.x)return Integer.compare(x,p.x);
            return Integer.compare(y,p.y);
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    long mod = (long)1e9+7, IINF = (long)1e18;
    final int INF = (int)1e9, MX = (int)3e5+2;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        int T = (multipleTC)?ni():1;
        //Solution Credits: Taranpreet Singh
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}