#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair PII; typedef vector VI; typedef vector VVI; #define MP make_pair #define PB push_back #define inf 1000000007 #define mod 1000000007 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define int long long template class segtree{ private: int n,sz; vector node; public: segtree(vector& v) : sz((int)v.size()){ n = 1; while(n < sz){ n *= 2; } node.resize(2*n-1,0); for(int i = 0; i < sz; i++){ node[i+n-1] = v[i]; } for(int i=n-2; i>=0; i--){ node[i] = node[i*2+1]+node[i*2+2]; } } void update(int k,T a){ k += n-1; node[k] = a; while(k>0){ k = (k-1)/2; node[k] = node[2*k+1]+node[2*k+2]; } } T query(int a,int b,int k=0,int l=0,int r=-1){ if(r < 0) r = n; if(r <= a || b <= l){ return 0; } if(a <= l && r <= b){ return node[k]; }else{ T vl = query(a,b,2*k+1,l,(l+r)/2); T vr = query(a,b,2*k+2,(l+r)/2,r); return vl+vr; } } void print(){ for(int i = 0; i < sz; i++){ cout<> n >> q; vectora(n); rep(i,n)cin >> a[i]; vectorb(n,1); segtreesg(a),sg2(b); vector,pair > >s; rep(i,n){ s.push_back(MP(MP(a[i],i),MP(0,0))); } rep(i,q){ int a,b,c,d; cin >> a >> b >> c >> d; s.push_back(MP(MP(d,inf+i),MP(b,c))); } sort(s.begin(),s.end()); vector res(q); rep(i,n+q){ if(s[i].first.second