#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
string min(string a,string b){
	return a<b?a:b;
}
struct tr{
	string len;
	string k;
}tre[200005];
string s[50010],ans,an,cnt;
void push_up(int f){
	if(tre[ls(f)].k>tre[rs(f)].k){
		tre[f].k=tre[ls(f)].k;
		tre[f].len=tre[ls(f)].len;
	}
	else{
		tre[f].k=tre[rs(f)].k;
		tre[f].len=tre[rs(f)].len;
	}
}
void build(int f,int l,int r){
	if(l==r){
		tre[f].k=s[f];
		for(int i=0;i<tre[f].k.length();i++) tre[f].k[i]=tolower(tre[f].k[i]);
		an=min(an,tre[f].k);
		tre[f].len=s[f]; 
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(f),l,mid);
	build(rs(f),mid+1,r);
	push_up(f);
}
void query(int f,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		if(tre[f].k>an){
			an=tre[f].k;
			ans=tre[f].len;
			cout<<l<<" "<<r<<endl;
		}
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) query(ls(f),l,mid,x,y);
	if(y>mid) query(rs(f),mid+1,r,x,y);
}
int n,m,x,y;
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> s[i];
	}
	build(1,1,n);
	cnt=an;
//	cout << "tips: " << cnt << endl;
	for(int i=1;i<=m;i++){
		cin >> x >> y;
		an=cnt;
		query(1,1,n,x,y);
		cout << ans << endl;
	}
	return 0;
}