题目描述

给定长度为$n$的序列$a_i$，以及$m$个询问，每次询问给出一个区间$[l,r]$，你需要回答$gcd(a_l,a_{l+1},…,a_r)$的值。

其中$gcd(a_l,a_{l+1},…,a_r)$表示$a_l,a_{l+1},…,a_r$的最大公约数。

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$a_i$； 接下来$m$行，每行输入两个整数$l,r$，表示一次询问。

输出格式

输出共$m$行，每行输出一个整数，依次表示每一次询问的结果。

样例输入 #1

5 3
6 4 8 12 24
1 3
2 3
3 5

样例输出 #1

2
4
4

说明/提示

保证$1\leq n,m\leq 10^5,1\leq a_i\leq 10^9,1\leq l\leq r\leq n$。