#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int logn=20;
int n,m,f[N][logn],log1[N];
struct qq{
string s;
string s1;
}a[N];
int bj(int x,int y){
/*if(a[x].s>a[y].s)return x;
else return y;*/
int i=0;
while(x/*i<=a[x].s.length()&&i<=a[y].s.length()*/){
if(i>a[x].s.length())return y;
if(i>a[y].s.length())return x;
int xx=a[x].s[i],yy=a[y].s[i];
//cout<<endl<<a[x].s.length()<<" "<<a[y].s.length()<<" "<<xx<<" "<<yy<<endl;
if(xx<yy)return y;
if(xx>yy)return x;
i++;
}
}
void print(int x){
cout<<a[x].s1<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
//scanf("%s",a[i].s_str());
cin>>a[i].s;
a[i].s1=a[i].s;
int l=sizeof(a[i].s);
for(int j=0;j<l;j++){
if(a[i].s[j]>='a'&&a[i].s[j]<='z')a[i].s[j]-=32;
}
/*for(int j=0;j<=a[i].s1.length();j++){
if(a[i].s1[j]>'Z'){
a[i].s[j]=a[i].s1[j]-32;
}
else a[i].s[j]=a[i].s1[j];
//cout<<a[i].s[j];
}*/
//cout<<a[i].s1<<endl;
//cout<<a[i].s<<endl;
}
log1[0]=-1;
for(int i=1;i<=n;i++){
log1[i]=log1[i>>1]+1;
f[i][0]=i;
}
for(int j=1;j<=logn;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
//cout<<f[i][j-1]<<" "<<f[i+(1<<j-1)][j-1]<<" ";
f[i][j]=bj(f[i][j-1],f[i+(1<<j-1)][j-1]);
//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
}
while(m--){
int x,y;
scanf("%d%d",&x,&y);
int s=log1[y-x+1];
int ans=bj(f[x][s],f[y-(1<<s)+1][s]);
print(ans);
}
return 0;
}
十个全部re 但看不出来