給定一行n個正整數a[1]…a[n]。

m次詢問，每次詢問給定一個區間[L,R]，輸出a[L]~a[R]的大公因數。

第一行兩個整數n，m。

第二行n個整數表示a[1]…a[n]。

以下m行，每行2個整數表示詢問區間的左右端點。

保證輸入數據合法。

共m行，每行表示一個詢問的答案。

5 3 4 12 3 6 7 1 3 2 3 5 5

1 3 7

對于30%的數據，n<= 100， m<= 10

對于60%的數據，m<= 1000

對于100%的數據，1<= n<= 1000，1<= m<= 1,000,000

0< 數字大小<= 1,000,000,000

我們看題不難發現題目是尋找a[L]~a[R]這片區間之內的一個最值問題。不過這題中是求區間內的大公因數，區間！所以，要求：多次求解連續區域 a ～ b a\sim b a～b 的大公因數。我們能想到什么？很明顯！求區間最值問題的ST表,ST表不懂的看這里。

#includeusing namespace std;

typedef long long ll;
const int N = 100010;

int maxn[N][50];    //區間大值表
int lg[N];  //lg函數,其實就是課上講的Log[N]

inline int read(){//快速輸入
    int x = 0,f=1;char ch = getchar();
    while(ch< '0' || ch >'9') {if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch<= '9'){x = x*10 + ch - '0'; ch = getchar();}
    return x*f;
}

int main(){int n,m;
    n = read(); m = read();

    for(int i = 1;i<=n;i++){//初始化
        maxn[i][0] = read();
    }

    for(int i = 2;i<=n;i++){//以2為底的lg求出來 ,最少要求到lgn，因為我們是通過2^i去倍增區間長度的
        lg[i] = lg[i/2] + 1;
    }

    for(int i = 1;i<=lg[n];i++)     //建立st表，第一維是區間起始位置，第二維終止位置是2^i-1
        for(int j = 1;j + (1<maxn[j][i] = max(maxn[j][i-1],maxn[j+(1<<(i-1))][i-1]);
        }

    int l,r;
    while(m--){l = read(); r = read();

        int len = lg[r-l+1];

        //查詢，求兩個子區間的并集，，第二個區間的左端點，這個端點我們不知道
        //就假設它為x，那么x + (1<

int gcd(int a,int b)
{int r=a%b;
	while(r>0)
	{a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);//遞歸+三目運算符
}

#includeusing namespace std;
const int N = 1e5+5;
int st[N][20];
int logg[N];
int n,m;
int gcd(int a,int b)
{if(b==0) return a;
	else return gcd(b,a%b);	
} 
int main()
{	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){scanf("%d",&st[i][0]);
	}
	for(int i=2;i<=n;i++) logg[i]=logg[i/2]+1;
	
	for(int j=1;j<=logg[n];j++){for(int i=1;i+(1<	st[i][j]=gcd(st[i][j-1],st[i+(1<scanf("%d%d",&l,&r);
		int x=logg[r-l+1];
		printf("%d\n",gcd(st[l][x],st[r-(1<