You are given n segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every k ∈ [1..n], calculate the number of points with integer coordinates such that the number of segments that cover these points equals k. A segment with endpoints l_i and r_i covers point x if and only if l_i ≤ x ≤ r_i.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of segments.

The next n lines contain segments. The i-th line contains a pair of integers l_i, r_i (0 ≤ l_i ≤ r_i ≤ 10^{18}) — the endpoints of the i-th segment.

Output

Print n space separated integers cnt_1, cnt_2, ..., cnt_n, where cnt_i is equal to the number of points such that the number of segments that cover these points equals to i.

Examples

Input

3
0 3
1 3
3 8


Output

6 2 1 


Input

3
1 3
2 4
5 7


Output

5 2 0 

Note

The picture describing the first example:

<image>

Points with coordinates [0, 4, 5, 6, 7, 8] are covered by one segment, points [1, 2] are covered by two segments and point [3] is covered by three segments.

The picture describing the second example:

<image>

Points [1, 4, 5, 6, 7] are covered by one segment, points [2, 3] are covered by two segments and there are no points covered by three segments.
import java.io.*;
import java.util.*;
import java.lang.*;
import java.util.HashMap;
public class templ implements Runnable {
    class pair
    {
        int first,second;
        pair(int f,int s)
        {
            first=f;
            second=s;
        }
    }
    public static ArrayList<Integer> g[]=new ArrayList[1000000];
    public static int vis[]=new int[1000000];
    void dfs(int n,int par)
    {
        vis[n]=1;
        for(int i=0;i<g[n].size();i++)
        {
            int u=g[n].get(i);
            if(vis[u]==0)
                dfs(u,n);
        }
    }
    int binarySearch(int arr[], int l, int r, int x)
    {
        if (r >= l)
        {
            int mid = l + (r - l)/2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, l, mid-1, x);
            return binarySearch(arr, mid+1, r, x);
        }
        return -1;
    }
    void merge1(int arr[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int [n1];
        int R[] = new int [n2];
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i]<=R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    void sort1(int arr[], int l, int r)
    {
        if (l < r)
        {
            int m = (l+r)/2;
            sort1(arr, l, m);
            sort1(arr , m+1, r);
            merge1(arr, l, m, r);
        }
    }
    void merge3(int arr[],int arr1[],int arr2[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int [n1];
        int R[] = new int [n2];
        int L1[]=new int[n1];
        int R1[]=new int[n2];
        int L2[]=new int[n1];
        int R2[]=new int[n2];
        //long L3[]=new long[n1];
        //long R3[]=new long[n2];
        for (int i=0; i<n1; ++i)
        {
            L[i] = arr[l + i];
            L1[i]=arr1[l+i];
            L2[i]=arr2[l+i];
            //L3[i]=arr3[l+i];
        }
        for (int j=0; j<n2; ++j)
        {
            R[j] = arr[m + 1+ j];
            R1[j]=arr1[m+1+j];
            R2[j]=arr2[m+1+j];
            //R3[j]=arr3[m+1+j];
        }
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                arr1[k]=L1[i];
                arr2[k]=L2[i];
                //arr3[k]=L3[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                arr1[k]=R1[j];
                arr2[k]=R2[j];
                //arr3[k]=R3[j];
                j++;
            }
            k++;
        }
        while (i < n1)
        {
            arr[k] = L[i];
            arr1[k]=L1[i];
            arr2[k]=L2[i];
            //arr3[k]=L3[i];
            i++;
            k++;
        }
        while (j < n2)
        {
            arr[k] = R[j];
            arr1[k]=R1[j];
            arr2[k]=R2[j];
            //arr3[k]=R3[j];
            j++;
            k++;
        }
    }
    void sort3(int arr[],int arr1[],int arr2[], int l, int r)
    {
        if (l < r)
        {
            int m = (l+r)/2;
            sort3(arr,arr1,arr2, l, m);
            sort3(arr ,arr1,arr2, m+1, r);
            merge3(arr,arr1,arr2,l, m, r);
        }
    }
    void merge2(long arr[],int arr1[],int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        long L[] = new long [n1];
        long R[] = new long [n2];
        int L1[]=new int[n1];
        int R1[]=new int[n2];
        for (int i=0; i<n1; ++i)
        {
            L[i] = arr[l + i];
            L1[i]=arr1[l+i];
        }
        for (int j=0; j<n2; ++j)
        {
            R[j] = arr[m + 1+ j];
            R1[j]=arr1[m+1+j];
        }
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                arr1[k]=L1[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                arr1[k]=R1[j];
                j++;
            }
            k++;
        }
        while (i < n1)
        {
            arr[k] = L[i];
            arr1[k]=L1[i];
            i++;
            k++;
        }
        while (j < n2)
        {
            arr[k] = R[j];
            arr1[k]=R1[j];
            j++;
            k++;
        }
    }
    void sort2(long arr[],int arr1[],int l, int r)
    {
        if (l < r)
        {
            int m = (l+r)/2;
            sort2(arr,arr1, l, m);
            sort2(arr ,arr1, m+1, r);
            merge2(arr,arr1,l, m, r);
        }
    }
    void merge4(int arr[],int arr1[],int arr2[],int arr3[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int [n1];
        int R[] = new int [n2];
        int L1[]=new int[n1];
        int R1[]=new int[n2];
        int L2[]=new int[n1];
        int R2[]=new int[n2];
        int L3[]=new int[n1];
        int R3[]=new int[n2];
        for (int i=0; i<n1; ++i)
        {
            L[i] = arr[l + i];
            L1[i]=arr1[l+i];
            L2[i]=arr2[l+i];
            L3[i]=arr3[l+i];
        }
        for (int j=0; j<n2; ++j)
        {
            R[j] = arr[m + 1+ j];
            R1[j]=arr1[m+1+j];
            R2[j]=arr2[m+1+j];
            R3[j]=arr3[m+1+j];
        }
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                arr1[k]=L1[i];
                arr2[k]=L2[i];
                arr3[k]=L3[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                arr1[k]=R1[j];
                arr2[k]=R2[j];
                arr3[k]=R3[j];
                j++;
            }
            k++;
        }
        while (i < n1)
        {
            arr[k] = L[i];
            arr1[k]=L1[i];
            arr2[k]=L2[i];
            arr3[k]=L3[i];
            i++;
            k++;
        }
        while (j < n2)
        {
            arr[k] = R[j];
            arr1[k]=R1[j];
            arr2[k]=R2[j];
            arr3[k]=R3[j];
            j++;
            k++;
        }
    }
    void sort4(int arr[],int arr1[],int arr2[],int arr3[], int l, int r)
    {
        if (l < r)
        {
            int m = (l+r)/2;
            sort4(arr,arr1,arr2,arr3, l, m);
            sort4(arr ,arr1,arr2,arr3, m+1, r);
            merge4(arr,arr1,arr2,arr3,l, m, r);
        }
    }
    public int justsmall(int a[],int l,int r,int x)
    {
        int p=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[mid]<=x)
            {
                p=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        return p;
    }
    public int justlarge(int a[],int l,int r,int x)
    {
        int p=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[mid]<=x)
            {
                l=mid+1;
            }
            else
            {
                p=a[mid];
                r = mid - 1;
            }
        }
        return p;
    }
    long gcd(long x,long y)
    {
        if(x%y==0)
            return y;
        else
            return(gcd(y,x%y));
    }
    long fact(long n)
    {
        long ans=1;
        for(int i=1;i<=n;i++)
            ans*=i;
        return ans;
    }
    public static void main(String args[])throws Exception
    {
        new Thread(null,new templ(),"templ",1<<26).start();
    }
    public void run() {
        try
        {
            InputReader in = new InputReader(System.in);
            PrintWriter out = new PrintWriter(System.out);
            templ ob=new templ();
            int n=in.ni();
            long m[]=new long[2*n];
            int a[]=new int[2*n];
            int o=0;
            for(int i=1;i<=n;i++)
            {
                long l=in.nl();
                long r=in.nl();
                if(l==r)
                {
                    m[o]=l;
                    a[o]=0;
                    o++;
                    continue;
                }
                m[o]=l;
                a[o]=1;
                o++;
                m[o]=r;
                a[o]=-1;
                o++;
            }
            sort2(m,a,0,o-1);
            int open=0;
            long ans[]=new long[n+1];
            for(int i=0;i<o;i++)
            {
                if(i!=0)
                {
                    long k=m[i]-m[i-1]-1;
                    if(open<=n)
                        ans[open]+=k;
                }
                int j;
                int c=0;
                int op=0;
                for(j=i;j<o;j++)
                {
                    if(m[i]!=m[j])
                        break;
                    op+=a[j];
                    if(a[j]==1||a[j]==0)
                        c++;
                }
                if(open+c<=n)
                    ans[open+c]++;
                open+=op;
                i=j-1;
            }
            for(int i=1;i<=n;i++)
                out.print(ans[i]+" ");
            out.close();
        }
        catch(Exception e){
            return;
        }
    }
    static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

    }
}