### 题解

#include<bits/stdc++.h>
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define N 300005
#define inf 1000000005
#define ls t[u].s[0]
#define rs t[u].s[1]
#define pb push_back
int n, m, block[N], sq1, b[N], a[N], belong[N], sq2;
struct node{
int l, r, a, b, id;
friend bool operator < (node x, node y)
{
return belong[x.l] != belong[y.l] ? belong[x.l] < belong[y.l] : belong[x.l] & 1 ? x.r > y.r : x.r < y.r;
}
}t[N];
struct ques{
int x, y;
}ans[N];
int tot, cnt[N], cnt2[N], c[N];
inline ques calc (int l, int r)
{
ques ret = (ques) {0, 0};
if (block[l] == block[r])
{
fo (i, l, r)
{
ret.x += c[i];
ret.y += (bool) c[i];
}
return ret;
}
int bl = block[l] + 1, br = block[r] - 1;
fo (i, bl, br)
{
ret.x += cnt[i];
ret.y += cnt2[i];
}
bl = bl * sq1 - 1;
fo (i, l, bl)
{
ret.x += c[i];
ret.y += (bool) c[i];
}
br = (br + 1) * sq1;
fo (i, br, r)
{
ret.x += c[i];
ret.y += (bool) c[i];
}
return ret;
}
inline void add (int col, bool flag)
{
if (flag)
{
if (!c[col]) ++cnt2[block[col]];
++c[col];
++cnt[block[col]];
}
else
{
--c[col];
--cnt[block[col]];
if (!c[col]) --cnt2[block[col]];
}
}
int main ()
{
scanf("%d %d", &n, &m);
sq2 = std::max((int) (n / sqrt(1.0 * m * 2 / 3)), 1);
fo (i, 1, n) belong[i] = i / sq2;
fo (i, 1, n) {scanf("%d", &a[i]); b[i] = a[i];}
tot = n;
fo (i, 1, m)
{
scanf("%d %d %d %d", &t[i].l, &t[i].r, &t[i].a, &t[i].b);
b[++tot] = t[i].a; b[++tot] = t[i].b;
t[i].id = i;
}
std::sort(b + 1, b + tot + 1);
tot = std::unique(b + 1, b + tot + 1) - b - 1;
sq1 = (int) sqrt(tot);
fo (i, 1, tot) block[i] = i / sq1;
fo (i, 1, n) a[i] = std::lower_bound(b + 1, b + tot + 1, a[i]) - b;
fo (i, 1, m)
{
t[i].a = std::lower_bound(b + 1, b + tot + 1, t[i].a) - b;
t[i].b = std::lower_bound(b + 1, b + tot + 1, t[i].b) - b;
}
std::sort(t + 1, t + m + 1);
int L = 1, R = 0;
fo (i, 1, m)
{
while (t[i].l < L) {--L; add(a[L], 1);}
while (t[i].r > R) {++R; add(a[R], 1);}
while (t[i].l > L) {add(a[L], 0); ++L;}
while (t[i].r < R) {add(a[R], 0); --R;}
ans[t[i].id] = calc(t[i].a, t[i].b);
}
fo (i, 1, m) printf("%d %d\n", ans[i].x, ans[i].y);
return 0;
}