#include <bits/stdc++.h>
using namespace std;
const int Maxn=1000005;
int n,q,num[Maxn],belong[Maxn];
long long ans[3][Maxn],cnt[3][Maxn];
const int p=20180623;
struct quest
{
    int id,l1,r1,l2,r2,x;
    bool operator < (const quest &tmp)const
    {
        if(belong[l1]!=belong[tmp.l1]) return belong[l1]<belong[tmp.l1];
        if(belong[r1]!=belong[tmp.r1]) return belong[r1]<belong[tmp.r1];
        if(belong[l2]!=belong[tmp.l2]) return belong[l2]<belong[tmp.l2];
        if(belong[r2]!=belong[tmp.r2]) return belong[r2]<belong[tmp.r2];
        return false;
    }
}Q[Maxn];
void dec1(int x)
{
    cnt[1][num[x]]--; 
}
void dec2(int x)
{
    cnt[2][num[x]]--;
}
void inc1(int x)
{
    cnt[1][num[x]]++;
}
void inc2(int x)
{
    cnt[2][num[x]]++;
}
void HeadMo()
{
    int l1=1,r1=0,l2=1,r2=0;
    for(int i=1;i<=q;i++)
    {
        while(l1<Q[i].l1) dec1(l1++);
        while(l1>Q[i].l1) inc1(--l1);
        while(r1<Q[i].r1) inc1(++r1);
        while(r1>Q[i].r1) dec1(r1--);
        while(l2<Q[i].l2) dec2(l2++);
        while(l2>Q[i].l2) inc2(--l2);
        while(r2<Q[i].r2) inc2(++r2);
        while(r2>Q[i].r2) dec2(r2--);
        ans[1][Q[i].id]=cnt[1][Q[i].x];
        ans[2][Q[i].id]=cnt[2][Q[i].x];
    }
    for(int i=1;i<=q;i++)
    {
        printf("%lld\n%lld\n%lld\n",ans[1][i],ans[2][i],ans[1][i]*ans[2][i]%p);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    int bloc=pow(n,0.6666666);
    for(int i=1;i<=n;i++) belong[i]=(i-1)/bloc+1;
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d%d%d",&Q[i].l1,&Q[i].r1,&Q[i].l2,&Q[i].r2,&Q[i].x);
        Q[i].id=i;
    }
    sort(Q+1,Q+1+q);
    HeadMo();
    return 0;
}