#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,a[N],lg[N];
int f[N][25];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][0]=a[i];
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		int len=r-l+1;
		int j=lg[len];
		if(f[l][j]>f[r-(1<<j)+1][j])cout<<f[r-(1<<j)+1][j]<<" ";
		else cout<<f[l][j]<<" ";
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e6+5;
int n,m,a[N];
int lg[N],f[N][30];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][0]=a[i];
	}
	for(int j=1;j<=25;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int l,r;
		r=i-1;
		if(r>=m)l=r-m+1;
		else l=1;
		int len=r-l+1,j=lg[len];
		if(f[l][j]>f[r-(1<<j)+1][j])cout<<f[r-(1<<j)+1][j]<<endl;
		else cout<<f[l][j]<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,a[N],lg[N],xiao[N][25],da[N][25];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	cin>>a[1];
	xiao[1][0]=1;
	da[1][0]=1;
	for(int i=2;i<=n;i++){
		cin>>a[i];
		xiao[i][0]=i;
		da[i][0]=i;
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			int a1=xiao[i][j-1],b1=xiao[i+(1<<j-1)][j-1],a2=da[i][j-1],b2=da[i+(1<<j-1)][j-1];
			if(a[a1]>a[b1])xiao[i][j]=b1;
			else xiao[i][j]=a1;
			if(a[a2]>a[b2])da[i][j]=a2;
			else da[i][j]=b2;
		}
	}
	while(m--){
		int l,r,x;
		cin>>l>>r>>x;
		int len=r-l+1,j=lg[len],mi,ma;
		if(a[xiao[l][j]]>a[xiao[r-(1<<j)+1][j]]){
			mi=xiao[r-(1<<j)+1][j];
		}
		else mi=xiao[l][j];
		if(a[da[l][j]]>a[da[r-(1<<j)+1][j]]){
			ma=da[l][j];
		}
		else ma=da[r-(1<<j)+1][j];
		if(a[ma]==x&&a[mi]==x)cout<<-1<<endl;
		else if(a[ma]!=x)cout<<ma<<endl;
		else if(a[mi]!=x)cout<<mi<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,m,lg[100005];
string f[N][20],a[N];
map<string,string>mp; 
string xiao(string s){
	string x=s;
	for(int i=0;i<x.size();i++){
		if(x[i]>='A'&&x[i]<='Z')x[i]+=' ';
	}
	return x;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]=xiao(a[i]);
	}
	for(int i=1;i<=n;i++)f[i][0]=a[i];
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			string s1=f[i][j-1];
			string s2=f[i+(1<<(j-1))][j-1];
			if(mp[s1]>mp[s2])f[i][j]=f[i][j-1];
			else f[i][j]=f[i+(1<<(j-1))][j-1];
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		int len=r-l+1;
		int j=lg[len];
		string ans;
        if(mp[f[l][j]]>mp[f[r-(1<<j)+1][j]])ans=f[l][j];
        else ans=f[r-(1<<j)+1][j];
		cout<<ans<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,m,d,t,f[N][20],a[N],lg[N];
int cinn(int l,int r){
	int j=lg[r-l+1];
	int ans;
	ans=max(f[l][j],f[r-(1<<j)+1][j]);
	return ans;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>m>>d;
	for(int i=2;i<=m;i++)lg[i]=lg[i/2]+1;
	while(m--){
		char c;
		int x;
		cin>>c>>x;
		if(c=='A'){
			n++;
			a[n]=(t+x)%d;
			int j=0;
			while((1<<j)<=n){
				int i=n-(1<<j)+1;
				if(j==0)f[i][j]=a[n];
				else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
				j++;
			}
		}
		if(c=='Q'){
			t=cinn(n-x+1,n);
			cout<<t<<endl;
		}

	}

	return 0;
}