#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,mxm=3e4+10;
int n,m,a[N],d[N],bl,cnt=0,ans[N],idx=0,b[N],t[N];
struct node
{
	int l,r,id;
}q[N];
bool cmp(node x,node y)
{
	return (d[x.l]^d[y.l]?d[x.l]<d[y.l]:x.r<y.r);
}
bitset<N>sum[mxm+500],s;
void del(int x)
{
	t[x]--;
	s.reset(x+t[x]);
}
void add(int x)
{
	s.set(x+t[x]);
	t[x]++;
}
void solve()
{
	if(m==0)return;
	idx=cnt=0;
	for(;cnt<=mxm-10&&m;m--)
	{
		if(cnt<mxm-10&&m)cnt++;
		sum[cnt].set();
		for(int j=1,l,r;j<=3;j++)
		{
			cin>>l>>r;
			ans[cnt]+=r-l+1;
			q[++idx]=(node){l,r,cnt};
		}
	}
	sort(q+1,q+idx+1,cmp);
	for(int i=1,l=1,r=0,ql,qr;i<=idx;i++)
	{
		ql=q[i].l,qr=q[i].r;
		while(l>ql)add(a[--l]);
		while(r<qr)add(a[++r]);
		while(l<ql)del(a[l++]);
		while(r>qr)del(a[r--]);
		sum[q[i].id]&=s;
	}
	for(int i=1;i<=cnt;i++)
	{
		cout<<ans[i]-(int)sum[i].count()*3<<'\n';
	}
	return;
}
int main()
{
	cin>>n>>m;
	bl=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		d[i]=(i-1)/bl;
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	int T=3;
	while(T--)
	{
		solve();
		memset(t,0,sizeof t);	
	}
	return 0;
}