#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define lb(a,b,c) lower_bound(a,b,c)
#define ub(a,b,c) upper_bound(a,b,c)
using namespace std;
int n,_m;
struct MT{
    int l,r,s[10000]; MT *L,*R;
    MT(){ l=r=0; L=R=0; }
}* rt;
int dx(int* s,int r,int k,int l=0){
    for(int m;l<r;){
        m=l+r+1>>1;
        if(s[m]<=k) l=m; else r=m-1;
    }
    while(r&&s[r-1]>=k) r--;
    return r;
}
int dy(int* s,int b,int k,int l=0){
    int r=b;
    for(int m;l<r;){
        m=l+r+1>>1;
        if(s[m]<=k) l=m; else r=m-1;
    }
    while(r<=b&&s[r+1]<=k) r++;
    return r;
}
void build(int l,int r,MT* w){
    w->l=l; w->r=r;
    //w.s=(int*)malloc((r-l+1)<<2);
    if(l==r){ scanf("%d",w->s); return; }
    int m=l+r>>1,i,j,t;
    build(l,m,w->L=new MT());
    build(m+1,r,w->R=new MT());
    for(i=0,j=0,t=0;i<=m-l&&j<r-m;)
        if(w->L->s[i]<w->R->s[j]) 
            w->s[t++]=w->L->s[i++];
        else w->s[t++]=w->R->s[j++];
    if(i<=m-l) w->s[t++]=w->L->s[i++];
    if(j<r-m) w->s[t++]=w->R->s[j++];
}
int query(MT& w,int l,int r,int x,int y){
    if(l<=w.l && w.r<=r){
        int c1=ub(w.s,w.s+w.r-w.l+1,y)-w.s;
        int c2=lb(w.s,w.s+w.r-w.l+1,x)-w.s;
        printf("%d %d\n",c1,c2);
        return c1-c2;
    }
    int m=w.l+w.r>>1,ans=0;
    if(l<=m) ans+=query(*w.L,l,r,x,y);
    if(m< r) ans+=query(*w.R,l,r,x,y);
    return ans;
}
int main(){
    scanf("%d%d",&n,&_m); rt=new MT();
    build(1,n,rt);
    for(int i=0;i<5;++i) printf("%d \n",rt->s[i]);
    for(int a,b,c,d,i=0;i<_m;++i){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d\n",query(*rt,a,b,c,d));
    }
}