#include<cstdio>
#define M 10000000
#define N(x,y) (x<y?x:y)
int n,m,i,j,b[18][100001],c[100001],o,l;
char r[M],p[30];
int A()
{
  	int s=0;
  	for(;p[o]<'0'||p[o]>'9';o++);
  	for(;p[o]>='0'&&p[o]<='9';o++)
  		s=s*10+p[o]-'0';
  	return s;
}
void S(int x)
{
    int i,d=x>99999?7:x>9999?6:x>999?5:x>99?4:x>9?3:2;
    for(i=d;--i;x/=10)
        r[l+i]=x%10+48;
    r[l=l+d]=10;
}
int main()
{
    freopen("rmq.in","r",stdin),freopen("rmq.out","w",stdout),fgets(p,30,stdin),n=A(),m=A();
    for(i=1;i<=n;i++)
        fgets(p,30,stdin),o=0,b[0][i]=A();
	for(i=2;i<=n;i++)
		c[i]=c[i/2]+1;
    for(i=1;(1<<i)<=n;i++)
    	for(j=1;j<=n+1-(1<<i);j++)
        	b[i][j]=N(b[i-1][j],b[i-1][j+(1<<(i-1))]);
    while(m--)
        fgets(p,30,stdin),o=0,i=A(),j=A(),n=c[j-i+1],S(N(b[n][i],b[n][j+1-(1<<n)]));
    fwrite(r,1,l,stdout);
}