#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+10;
const int M=405;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int s[M][N],vis[N],h[M][N],ans,l0,r0,iid[N],x,num;
int n,m,len,L[N],R[N],belong[N],cntt;
struct node{
	int num,st;
}p[M][M];
struct Node{
	int id,o,af;
}a[N];
inline bool cmp1(Node a,Node b){return a.o<b.o;}
inline bool cmp2(Node a,Node b){return a.id<b.id;}
int f(int l,int r)
{
	memset(vis,0,sizeof(vis));
	if(belong[l]==belong[r])
	{
		int t=0,re=0x3f3f3f3f;
		for(int i=l;i<=r;i++)
		{
			vis[a[i].af]++;
			if(t<vis[a[i].af]||(t==vis[a[i].af]&&re>a[i].af))
			{
				t=vis[a[i].af];
				re=a[i].af;
			}
		}
		return iid[re];
	}
	int t=p[belong[l]+1][belong[r]-1].num,re=p[belong[l]+1][belong[r]-1].st;
	for(int i=l;i<=R[belong[l]];i++)
	{
		if(vis[a[i].af]==0)vis[a[i].af]=vis[a[i].af]+s[belong[r]-1][a[i].af]-s[belong[l]][a[i].af];
		vis[a[i].af]++;
		if(vis[a[i].af]>t||(vis[a[i].af]==t&&re>a[i].af))
		{
			t=vis[a[i].af];
			re=a[i].af;
		}
	}
	for(int i=L[belong[r]];i<=r;i++)
	{
		if(vis[a[i].af]==0)vis[a[i].af]=vis[a[i].af]+s[belong[r]-1][a[i].af]-s[belong[l]][a[i].af];
		vis[a[i].af]++;
		if(vis[a[i].af]>t||(vis[a[i].af]==t&&re>a[i].af))
		{
			t=vis[a[i].af];
			re=a[i].af;
		}
	}
	return iid[re];
}
signed main()
{	
    n=read();m=read();
    len=sqrt(n);num=n/len;if(n%len)num++;
    memset(L,0x3f3f3f3f,sizeof(L));
    for(int i=1;i<=n;i++)
    {
    	a[i].o=read();a[i].id=i;
    	belong[i]=(i-1)/len+1;
    	L[belong[i]]=min(L[belong[i]],i);
    	R[belong[i]]=max(R[belong[i]],i);
    }
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
    	a[i].af=a[i-1].af;
    	if(a[i].o!=a[i-1].o)a[i].af++,cntt++;
    	iid[a[i].af]=a[i].o;
    	h[belong[a[i].id]][a[i].af]++;
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=cntt;i++)
    {
    	for(int j=1;j<=num;j++)
    	{
    		s[j][i]=s[j-1][i]+h[j][i];
    	}
    }
    for(int i=1;i<=num;i++)
    {
    	memset(vis,0,sizeof(vis));
    	for(int j=i;j<=num;j++)
    	{
    		int kk=0,kt=0;
    		for(int k=L[j];k<=R[j];k++)
    		{
    			vis[a[k].af]++;
    			if(vis[a[k].af]>kk)
    			{
    				kk=vis[a[k].af];
    				kt=a[k].af;
    			}
    		}
    		if(kk>vis[p[i][j-1].st]||(kk==vis[p[i][j-1].st]&&kt<p[i][j-1].st))
    		{
    			p[i][j].num=kk;
    			p[i][j].st=kt;
    		}
    		else
    		{
    			p[i][j].num=p[i][j-1].num;
    			p[i][j].st=p[i][j-1].st;
    		}
    	}
    }
    while(m--)
    {
    	l0=read();r0=read();
    	int l=((l0+x-1)%n)+1,r=((r0+x-1)%n)+1;
    	if(l>r)swap(l,r);
    	x=f(l,r);
    	cout<<l<<" "<<r<<" ";
    	cout<<x<<"\n";
    }
    return 0;
}