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.

双区间查询

第一个区间就裸的[1...l1-1] [l2..r2] 

   [1.......r1] [l2..r2]

      用vector （Q[i]）维护~(i为l1-1,r1的值)

       表示 [1...i][Q[i][j].l2...Q[i][j].r2] 表示上述~

第二个区间 当枚举i的时候，内循环枚举线段到s[p].x<=i，s[p].y加入a[]来维护终止点

  因为起止点排好序了

，

  一定满足Q[i]的[1....i]

  a[]树状数组来维护好l2,r2.

原理理解后 代码很简单。。

直接贴朱神的代码了

复杂度 比较难表述 但是显然是接受范围

（当初考虑l,r不好存。。开数组不好存，才知道可以表示在数组内就好）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int N=100000;int a[100005];int inline lowbit(int x){ return x&(-x);}void add(int p,int val){ while(p<=N){ a[p]=(a[p]+val); p+=lowbit(p); }}int sum(int p){ int ans=0; while(p>0){ ans=(ans+a[p]); p-=lowbit(p); } return ans;}struct Query{ int l,r; int oriid; int orip; Query(){} Query(int a,int b,int c,int d):l(a),r(b),oriid(c),orip(d){}};vector
             
               qs[100005];int ans[100005][2];struct Pair{ int x,y; Pair(){} Pair(int a,int b):x(a),y(b){} bool operator<(const Pair&b)const{ return x