我是数据结构白痴。

分块做法，WA了第一个subtask的第二个点，难受啊……

https://www.luogu.com.cn/record/48743910

/**************************************************************
 * Problem: 5012
 * Author: Vanilla_chan
 * Date: 20210331
 * E-Mail: Vanilla_chan@outlook.com
**************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<limits.h>
#define IL inline
#define re register
#define LL long long
#define ULL unsigned long long
#ifdef TH
#define debug printf("Now is %d\n",__LINE__);
#else
#define debug
#endif
#ifdef ONLINE_JUDGE
char buf[1<<23],* p1=buf,* p2=buf,obuf[1<<23],* O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
using namespace std;

namespace oi
{
	inline bool isdigit(const char& ch)
	{
		return ch<='9'&&ch>='0';
	}
	inline bool isalnum(const char& ch)
	{
		return (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9');
	}
	struct istream
	{
		char ch;
		bool fu;
		template<class T>inline istream& operator>>(T& d)
		{
			fu=d=0;
			while(!isdigit(ch)&&ch!='-') ch=getchar();
			if(ch=='-') fu=1,ch=getchar();
			d=ch-'0';ch=getchar();
			while(isdigit(ch))
				d=(d<<3)+(d<<1)+(ch^'0'),ch=getchar();
			if(fu) d=-d;
			return *this;
		}
		inline istream& operator>>(char& ch)
		{
			ch=getchar();
			for(;!isalnum(ch);ch=getchar());
			return *this;
		}
		inline istream& operator>>(string& str)
		{
			str.clear();
			for(;!isalnum(ch);ch=getchar());
			while(isalnum(ch))
				str+=ch,ch=getchar();
			return *this;
		}
	}cin;
	inline int read()
	{
		int x=0,fu=1;
		char ch=getchar();
		while(!isdigit(ch)&&ch!='-') ch=getchar();
		if(ch=='-') fu=-1,ch=getchar();
		x=ch-'0';ch=getchar();
		while(isdigit(ch)) { x=x*10+ch-'0';ch=getchar(); }
		return x*fu;
	}
	int G[55];
	template<class T>inline void write(T x)
	{
		int g=0;
		if(x<0) x=-x,putchar('-');
		do { G[++g]=x%10;x/=10; } while(x);
		for(int i=g;i>=1;--i)putchar('0'+G[i]);putchar('\n');
	}
};
using namespace oi;
#define N 1000010

int n,m;
int maxnum;
int a[N],f[N];
LL sze[N];
int getf(int x)
{
	if(f[x]==x) return x;
	return f[x]=getf(f[x]);
}
LL now;
int duan;
void merge(int x,int y)
{
	x=getf(x);
	y=getf(y);
	if(x==y) return;
	duan--;
	now-=sze[x]*sze[x];
	now-=sze[y]*sze[y];
	f[y]=x;
	sze[x]+=sze[y];
	sze[y]=0;
	now+=sze[x]*sze[x];
}
vector<int>pos[N];
struct node
{
	LL ans;
	LL x;
	node(LL defen=0,int xx=0)
	{
		ans=defen;
		x=xx;
	}
	IL bool operator>(const node &z)const
	{
		if(ans==0) return 0;
		if(z.ans==0) return 1;
		if(ans*z.x==z.ans*x) return x>z.x;
		return ans*z.x>z.ans*x;
	}
};
IL node max(const node &x,const node &y)
{
	return x>y?x:y;
}
/*
namespace Tree
{
	::node a[N];
	struct node
	{
		::node mx;
		#define mx(x) b[x].mx
	}b[N<<2];
	void upd(int p)
	{
		mx(p)=::max(mx(p<<1),mx(p<<1|1));
	}
	void build(int p,int l,int r)
	{
		if(l==r)
		{
			mx(p)=a[l];
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		upd(p);
	}
	::node ask(int p,int L,int R,int l,int r)
	{
		if(l<=L&&R<=r)
		{
			return mx(p);
		}
		int mid=L+R>>1;
		if(l<=mid&&r>mid) return max(ask(p<<1,L,mid,l,r),ask(p<<1|1,mid+1,R,l,r));
		if(l<=mid) return ask(p<<1,L,mid,l,r);
		else return ask(p<<1|1,mid+1,R,l,r);
	}
};
*/
namespace Block
{
	::node a[N],mx[2010];
	int L[2010],R[2010],belong[N];
	int s,block;
	void build()
	{
		s=sqrt(n);
		block=n/s;
		for(int i=1;i<=s;i++)
		{
			L[i]=block*(i-1)+1;
			R[i]=block*i;
		}
		R[s]=n;
		for(int i=1;i<=s;i++)
		{
			for(int j=L[i];j<=R[i];j++)
			{
				belong[j]=i;
				mx[i]=max(mx[i],a[j]);
			}
		}
	}
	::node ask(int l,int r)
	{
		::node ans;
		if(belong[r]-belong[l]<=3)
		{
			for(int i=l;i<=r;i++) ans=::max(ans,a[i]);
		}
		else
		{
			for(int i=belong[l]+1;i<=belong[r]-1;i++) ans=::max(ans,mx[i]);
			for(int i=l;i<=R[belong[l]];i++) ans=::max(ans,a[i]);
			for(int i=L[belong[r]];i<=r;i++) ans=::max(ans,a[i]);
		}
		return ans;
	}
}
void pre()
{
	for(int i=1;i<=n;i++)
	{
		f[i]=0;
		sze[i]=0;
	}
	for(int i=1;i<=n;i++) pos[a[i]].push_back(i);
	for(int i=1;i<=maxnum;i++)
	{
		for(unsigned int j=0;j<pos[i].size();j++)
		{
			f[pos[i][j]]=pos[i][j];
			sze[pos[i][j]]=1;
			now++;
			duan++;
			if(f[pos[i][j]-1]) merge(pos[i][j],pos[i][j]-1);
			if(f[pos[i][j]+1]) merge(pos[i][j],pos[i][j]+1);
		}
//		cout<<"x="<<i<<" "<<"duan="<<duan<<" pts="<<now<<endl;
		Block::a[duan]=max(Block::a[duan],node(now,i));
	}
}
LL lastans;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		maxnum=max(maxnum,a[i]);
	}
	pre();
//	Tree::build(1,1,n);
	Block::build();
	node ans;
	LL l,r,a,b,x,y;
	for(int i=1;i<=m;i++)
	{
		a=read()%n;
		b=read()%n;
		x=read()%n;
		y=read()%n;
		l=(a*lastans%n+x-1)%n+1;
		r=(b*lastans%n+y-1)%n+1;
		if(l>r) swap(l,r);
		ans=Block::ask(l,r);
		if(ans.ans)
		{
			cout<<ans.ans<<" "<<ans.x<<endl;
			cout<<l<<" "<<r<<" "<<lastans<<endl;
			lastans=ans.x*ans.ans%n;
		}
		else
		{
			cout<<"-1 -1"<<endl;
			cout<<l<<" "<<r<<" "<<lastans<<endl;
			lastans=1%n;
		}
		
	}
	return 0;
}