$O(nm)$ 算法都过了。。。

// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define int long long
using namespace std;
int read(){
  int s = 0, w = 1;
  char c = getchar();
  while(c < '0' || c > '9'){
    if(c == '-')w = -1;
    c = getchar();
  }
  while(c >= '0' && c <= '9'){
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * w;
}
void print(int x){
  if(x < 0){
    putchar('-');
    x = -x;
  }
  if(x >= 10)print(x / 10);
  putchar(x % 10 + '0');
  return;
}
const int NMax = 1e5;
const int BMax = 300;
int n, q, blen;
int a[NMax + 10];
int val[NMax + 10];
void add(int x){
  val[a[x]]++;
}
void del(int x){
  --val[a[x]];
}
struct Ask{
  int l, r, a, b, id, dd;
  friend bool operator < (Ask aa, Ask bb){
    if(aa.dd == bb.dd){
      if(aa.dd % 2)return aa.r < bb.r;
      else return aa.r > bb.r;
    }
    return aa.dd < bb.dd;
  }
};
Ask ask[NMax + 10];
int ans1[NMax + 10], ans2[NMax + 10];
signed main(){
  //freopen(".in","r",stdin);
  //freopen(".out","w",stdout);
  n = read(), q = read(); blen = sqrt(n);
  for(int i = 1; i <= n; i++){
    a[i] = read();
  }
  for(int i = 1; i <= q; i++){
    ask[i].l = read(), ask[i].r = read();
    ask[i].a = read(), ask[i].b = read();
    ask[i].id = i; ask[i].dd = ask[i].l / blen;
  }
  sort(ask + 1, ask + 1 + q);
  int l = 1, r = 0;
  for(int i = 1; i <= q; i++){
    while(l > ask[i].l)add(--l);
    while(r < ask[i].r)add(++r);
    while(l < ask[i].l)del(l++);
    while(r > ask[i].r)del(r--);
    for(int j = ask[i].a; j <= ask[i].b; j++){
      ans1[ask[i].id] += val[j];
      ans2[ask[i].id] += (bool)val[j];
    }
  }
  for(int i = 1; i <= q; i++){
    print(ans1[i]), putchar(' '), print(ans2[i]), putchar('\n');
  }
  return 0;
}