#include <bits/stdc++.h>
using namespace std;

const int maxn(1000005);

inline int read() {
    int f(1), x(0);
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
    return f * x;
}

int n, m, maxcol, A[maxn], siz, B[maxn];
int ans1[maxn], ans2[maxn];
int t[maxn], tmp, c[maxn], d[maxn];

struct Query {
    int l, r, a, b, id;

    bool operator<(const Query& a) const {
        if (B[l] ^ B[a.l]) return B[l] < B[a.l];
        if (B[l] & 1) return r < a.r;
        return r > a.r;
    }
} q[maxn];

int lowbit(int x) { return x & -x; }

void modify(int x, int k, int* e) {
    for (int i = x; i <= maxcol; i += lowbit(i)) {
        e[i] += k;
    }
}

int getsum(int x, int* e) {
    int res(0);
    for (int i = x; i; i -= lowbit(i)) {
        res += e[i];
    }
    return res;
}

inline void add(int x) {
    if (!t[x]++ == 1) modify(x, 1, d);
    modify(x, 1, c);
}

inline void del(int x) {
    if (!--t[x] == 1) modify(x, -1, d);
    modify(x, -1, c);
}

int main() {
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    
    n = read(), m = read();
    siz = sqrt(n);

    for (int i = 1; i <= n; ++i) {
        A[i] = read();
        maxcol = max(maxcol, A[i]);
        B[i] = (i - 1) / siz + 1;
    }

    for (int i = 1; i <= m; ++i) {
        q[i] = {read(), read(), read(), read(), i};
    }

    sort(q + 1, q + 1 + m);

    /* for (int i = 1; i <= m; ++i) {
        cout << q[i].l << ' ' << q[i].r << ' ' << q[i].a << ' ' << q[i].b << ' ' << q[i].id << '\n';
    } */

    int l(1), r(0);
    for (int i = 1; i <= m; ++i) {
        // cerr << "i = " << i << ' ';
        while (l > q[i].l) add(A[--l])/* , cerr << "A[" << l << "] = " << A[l] << '\n' */;
        while (r < q[i].r) add(A[++r])/* , cerr << "A[" << r << "] = " << A[r] << '\n' */;
        while (l < q[i].l) /* cerr << "A[" << l << "] = " << A[l] << '\n', */ del(A[l++]);
        while (r > q[i].r) /* cerr << "A[" << r << "] = " << A[r] << '\n', */ del(A[r--]);
        ans1[q[i].id] = getsum(q[i].b, c) - getsum(q[i].a - 1, c);
        ans2[q[i].id] = getsum(q[i].b, d) - getsum(q[i].a - 1, d);
        // cerr << '\n';
    }

    for (int i = 1; i <= m; ++i) {
        printf("%d %d\n", ans1[i], ans2[i]);
    }
}