#include<bits/stdc++.h>

using namespace std;

#define N 100010

#define TT 25000

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

struct query

{

    int l , r;

    int id;

} q[N];

int n , m , sz;

int cnt[N] , block[N] , ans[N] , l1[N] , r1[N] , l2[N] , r2[N] , l3[N] , r3[N] , a[N] , b[N];

bool vis[N];

bitset< N > tmp , f[TT + ];

template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }

template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }

template <typename T> inline void read(T &x)

{

   T f = ; x = ;

   char c = getchar();

   for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

   for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

   x *= f;

}

inline void add(int x)

{

    tmp[a[x] + cnt[a[x]]] = ;

    ++cnt[a[x]];

}

inline void dec(int x)

{

    tmp[a[x] + cnt[a[x]] - ] = ;

    --cnt[a[x]];

}

inline bool cmp(query a , query b)

{

    if (block[a.l] == block[b.l]) return a.r < b.r;

    else return a.l < b.l;

}

inline void solve(int l , int r)

{

    tmp.reset();

    memset(cnt ,  , sizeof(cnt));

    memset(vis , false , sizeof(vis));

    int len = ;

    for (int i = ; i <= TT; i++) f[i].reset();

    for (int i = l; i <= r; i++)

    {

        q[++len] = (query){l1[i] , r1[i] , i};

        ans[i] += r1[i] - l1[i] + ;

        q[++len] = (query){l2[i] , r2[i] , i};

        ans[i] += r2[i] - l2[i] + ;

        q[++len] = (query){l3[i] , r3[i] , i};

        ans[i] += r3[i] - l3[i] + ;

    }

    sort(q +  , q + len +  , cmp);

    int L = q[].l , R = q[].l - ;

    for (int i = ; i <= len; i++)

    {

        while (R < q[i].r)

        {

            add(R + );

            ++R;

        }

        while (R > q[i].r)

        {

            dec(R);

            --R;

        }

        while (L < q[i].l)

        {

            dec(L);

            ++L;

        }

        while (L > q[i].l)

        {

            add(L - );

            --L;

        }

        if (!vis[q[i].id - l + ])

        {

            vis[q[i].id - l + ] = true;

            f[q[i].id - l + ] = tmp;

        } else f[q[i].id - l + ] &= tmp;

    }

    for (int i = l; i <= r; i++)

        ans[i] -= f[i - l + ].count() * ;

}

int main()

{

    read(n); read(m);

    int size = (int)sqrt(n) + ;

    for (int i = ; i <= n; i++) block[i] = (i - ) / size + ;

    for (int i = ; i <= n; i++)

    {

        read(a[i]);

        b[i] = a[i];

    }

    sort(b +  , b + n + );

    for (int i = ; i <= n; i++) a[i] = lower_bound(b +  , b + n +  , a[i]) - b;

    for (int i = ; i <= m; i++)

    {

        read(l1[i]); read(r1[i]);

        read(l2[i]); read(r2[i]);

        read(l3[i]); read(r3[i]);

    }

    for (int i = ; i <= m; i += TT) solve(i , min(i + TT -  , m));

    for (int i = ; i <= m; i++) printf("%d\n" , ans[i]);

    return ;

}