#include<bits/stdc++.h>
using namespace std;    
const int N=50010;
int n,m;
string a[N];
struct AA
{
	string max;
	int l,r;
	
}t[N*4];
void build(int i,int l,int r)
{
	t[i].l=l,t[i].r=r;
	if(l==r)
	{
		t[i].max=a[l];
		return;
		
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	t[i].max=max(t[i*2].max,t[i*2+1].max);
	 
}
string ask(int i,int x,int y)
{
	if(t[i].l>=x&&t[i].r<=y)
	{
		return t[i].max;
		
	}
	int mid=t[i].l+t[i].r>>1;
	string ans;
	if(mid>=x)ans=ask(i*2,x,y);
	if(mid<y)ans=max(ask(i*2+1,x,y),ans);
	return ans;
}
int main()
{ 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for (int j=0;j<a[i].size();j++)
		{
            if (a[i][j]<='Z'&&a[i][j]>='A')a[i][j]=a[i][j]-'A'+'a'; 
        }
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<ask(1,l,r)<<endl;
	}
    return 0;
}