#include<bits/stdc++.h>
#define ld double
#define ll long long
#define MAXN 1500005
using namespace std;
ll n,m;
ll a[MAXN],sum,cnt,s[MAXN],id[MAXN],w[MAXN];
ll A,b,x,y,last;
struct node{
	ll id;
	ll v;
}tr[4*MAXN];
int fa[MAXN];
vector<int> q[MAXN];
bool operator > (node a,node b)
{
	if(a.v==-1) return 0;
	if(b.v==-1) return 1;
	if(a.v*b.id!=b.v*a.id) return a.v*b.id>b.v*a.id;
	return a.id>b.id;
}
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void p(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return ;
	fa[x]=y;
	cnt-=s[x]*s[x]+s[y]*s[y];
	s[y]+=s[x];
	cnt+=s[y]*s[y];
}
void build(int l,int r,int x)
{
	if(l==r)
	{
		tr[x].id=id[l];
		tr[x].v=w[l];
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	if(tr[x*2]>tr[x*2+1])	tr[x]=tr[x*2];
	else tr[x]=tr[x*2+1];
}
node query(int l,int r,int L,int R,int x)
{
	if(l>R||r<L) return (node){1,-1e9};
	if(l>=L&&r<=R) return tr[x];
	int mid=(l+r)/2;
	node t1=query(l,mid,L,R,x*2),t2=query(mid+1,r,L,R,x*2+1);
	if(t1.v==-1e9) return t2;
	if(t2.v==-1e9) return t1; 
	if(t1>t2) return t1;
	return t2;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),fa[i]=i,s[i]=1,q[a[i]].push_back(i),w[i]=-1;
	a[0]=a[n+1]=1e9;
	for(int i=1;i<=1e6;i++)
	{
		for(int j=0;j<q[i].size();j++)
		{
			cnt++;
			int pos=q[i][j],p1=0,p2=0;
			if(a[pos]>=a[pos-1]) p1=1;
			if(a[pos]>=a[pos+1]) p2=1;
			if(!p1&&!p2) sum++;
			if(p1&&p2) 
			{
				sum--,p(pos,pos-1),p(pos,pos+1);
				continue;
			}
			if(p1)
				p(pos,pos-1);
			if(p2) 
				p(pos,pos+1);
		}
		if(cnt*id[sum]>=w[sum]*i) w[sum]=cnt,id[sum]=i;
	}
	build(1,n,1);
	while(m--)
	{
		scanf("%lld%lld%lld%lld",&A,&b,&x,&y);
		A=(A%n+n)%n,b=(b%n+n)%n,x=(x%n+n)%n,y=(y%n+n)%n;
		int l=(A*last%n+x-1+n)%n+1,
		r=(b*last%n+y-1+n)%n+1;
		if(l>r) swap(l,r);
		
		node ans=query(1,n,l,r,1);
		if(ans.v==-1) printf("-1 -1\n");
		else printf("%lld %lld\n",ans.v,ans.id);
		printf("%d %d %lld\n",l,r,last);
		if(ans.v==-1) last=1%n;
		else last=ans.v%n*ans.id%n;
	}
	return 0;
}