#include <bits/stdc++.h>
using namespace std;
//
const int mx = 1e5 + 5;
const int S = 320;
//
struct query
{
    int l, r, a, b, id;
    //
    bool operator < (const query &other)
    {
        if (l / S != other.l / S)
            return l < other.l;
        return l / S & 1 ? r < other.r : r > other.r;
    }
};
//
int n, q, A[mx];
int cnt[mx];
pair<int, int> block[S], ans[mx];
query Q[mx];
//
void update (int pos, int val)
{
    if (pos == 0)
        return;
    //
    int id = pos / S;
    //
    block[id].first += val;
    if (cnt[pos] == 0)
        ++block[id].second;
    cnt[pos] += val;
    if (cnt[pos] == 0)
        --block[id].second;
}
void operator += (pair<int, int> &a, const pair<int, int> &b)
{
    a.first += b.first;
    a.second += b.second;
}
pair<int, int> get (int a, int b)
{
    int block_a = a / S, block_b = b / S;
    pair<int, int> res(0, 0);
    //
    if (block_a == block_b)
    {
        for (int i = a; i <= b; ++i)
            res += make_pair(cnt[i], cnt[i] > 0);
        return res;
    }
    ++block_a, ++b;
    for (int i = block_a; i < block_b; ++i)
        res += block[i];
    for (int i = a; i < block_a * S; ++i)
        res += make_pair(cnt[i], cnt[i] > 0);
    for (int i = block_b * S; i < b; ++i)
        res += make_pair(cnt[i], cnt[i] > 0);
    return res;
}
void calc (void)
{
    int l = 0, r = 0;
    //
    for (int i = 1; i <= q; ++i)
    {
        while (l < Q[i].l)
            update(A[l++], -1);
        while (l > Q[i].l)
            update(A[--l], 1);
        while (r < Q[i].r)
            update(A[++r], 1);
        while (r > Q[i].r)
            update(A[r--], -1);
        ans[Q[i].id] = get(Q[i].a, Q[i].b);
    }
}
//
void process (void)
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> A[i];
    for (int i = 1; i <= q; ++i)
        cin >> Q[i].l >> Q[i].r >> Q[i].a >> Q[i].b,
        Q[i].id = i;

    sort(Q + 1, Q + q + 1);
    calc();

    for (int i = 1; i <= q; ++i)
        cout << ans[i].first << ' ' << ans[i].second << '\n';
}
//
signed main (void)
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    process();
}