#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
map<string,int> mp1;
map<int,string> mp2;
string s[60000];
string so[60000];
int a[60000];
int n,m;
struct node
{
	int l,r;
	int val;
};
struct seg
{
	node t[60000*4];
	int max(int a,int b)
	{
		return a>b?a:b; 
	}
	void build(int k,int l,int r)
	{
		t[k].l=l;
		t[k].r=r;
		if(l==r)
		{
			t[k].val=a[l];
			return ;
		}
		int mid=(l+r)>>1;
		build(2*k,l,mid);
		build(2*k+1,mid+1,r);
		t[k].val=max(t[2*k].val,t[2*k+1].val);
	}
	int query(int k,int l,int r)
	{
		if(t[k].l>=l&t[k].r<=r) return t[k].val;
		int mid=(t[k].l+t[k].r)>>1;
		int ans=0;
		if(l<=mid) ans=max(ans,query(2*k,l,r));
		if(r>mid) ans=max(ans,query(2*k+1,l,r));
		return ans;
	}
}tree;
int main()
{
	cin>>n>>m; 
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		so[i]=s[i];
	}
	sort(so+1,so+1+n);
	for(int i=1;i<=n;i++)
	{
		mp1[so[i]]=i;
		mp2[i]=so[i];
	}
	for(int i=1;i<=n;i++) a[i]=mp1[s[i]];
	tree.build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<mp2[tree.query(1,l,r)]<<endl;
	}
	return 0;
}

保龄，全WA，样例能过