On the number axis, there are N lines. The two endpoints L and R of each line are integer. Give you M queries, each query contains two intervals: [L1,R1] and [L2,R2], can you count how many lines satisfy this property: L1≤L≤R1 and L2≤R≤R2?

Input

First line will be a positive integer N (1≤N≤100000) indicating the number of lines. Following the coordinates of the N lines‘ endpoints L and R will be given (1≤L≤R≤100000). Next will be a positive integer M (1≤M≤100000) indicating the number of queries. Following the four numbers L1,R1,L2 and R2 of the M queries will be given (1≤L1≤R1≤L2≤R2≤100000).

Output

For each query output the corresponding answer.

Sample Input

31 32 43 521 2 3 41 4 5 6

Sample Output

21

#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N=100010;struct Line{    int l,r;    bool operator<(const Line &rhs)const    {        if(l!=rhs.l)            return l<rhs.l;        return r<rhs.r;    }};struct query{    int k,r1,r2,flag,id;    query(int _k=0,int _r1=0,int _r2=0,int _flag=0,int _id=0):k(_k),r1(_r1),r2(_r2),flag(_flag),id(_id){}    bool operator<(const query &rhs)const    {        return k<rhs.k;    }};Line line[N];query Q[N<<1];int T[N],ans[N];void init(){    CLR(T,0);    CLR(ans,0);}void add(int k,int v){    while (k<N)    {        T[k]+=v;        k+=(k&-k);    }}int getsum(int k){    int ret=0;    while (k)    {        ret+=T[k];        k-=(k&-k);    }    return ret;}int main(void){    int n,m,i;    while (~scanf("%d",&n))    {        init();        for (i=0; i<n; ++i)            scanf("%d%d",&line[i].l,&line[i].r);        sort(line,line+n);        scanf("%d",&m);        int qcnt=0;        for (i=0; i<m; ++i)        {            int l1,r1,l2,r2;            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);            Q[qcnt++]=query(l1,l2,r2,0,i);            Q[qcnt++]=query(r1,l2,r2,1,i);        }        sort(Q,Q+qcnt);        int x=0;        for (i=0; i<qcnt; ++i)        {            while (line[x].l<=Q[i].k&&x<n)                add(line[x++].r,1);            if(Q[i].flag)                ans[Q[i].id]+=getsum(Q[i].r2)-getsum(Q[i].r1-1);            else            {                while (line[x-1].l>=Q[i].k&&x-1>=0)                {                    add(line[x-1].r,-1);                    --x;                }                ans[Q[i].id]-=getsum(Q[i].r2)-getsum(Q[i].r1-1);                while (line[x].l<=Q[i].k&&x<n)                {                    add(line[x].r,1);                    ++x;                }            }        }        for (i=0; i<m; ++i)            printf("%d\n",ans[i]);    }    return 0;}