#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
vector<string> vc;
//两个字符串比较
string  bigger(string a,string b){
    int sza=a.size();
    int szb=b.size();
    int Max=max(sza,szb);
    int Min=min(sza,szb);
    for(int i=0;i<Min;i++){
        if(a[i]>b[i])
        return a;
        else if(a[i]<b[i])
        return b;
    }
    if(sza>Min) return a;
    else if(szb>Min)
    return b;
    else
    return b;
}
string lastest(int begin,int end){//多个字符串比较
    string s=vc[begin-1];
    for(int i=begin;i<=end-1;i++){
        s=bigger(vc[i],s);
    }
    return s;
}
int main(){
    int N,M;
    cin>>N>>M;
    while(N--){
        string s;
        cin>>s;
        transform(s.begin(),s.end(),s.begin(),::tolower);
        vc.push_back(s);
    }
    int begin,end;
    while(M--){
        //比较计算，输出最大的
        cin>>begin>>end;
        if(begin>end) swap(begin,end);
        cout<<lastest(begin,end)<<endl;

    }
    return 0;
}