题目描述

给定长度为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问区间 $[l,r]$ 内所有数的最大公约数（gcd）。

输入格式

第一行两个整数 $n,m$；第二行 $n$ 个整数 $a_i$；接下来 $m$ 行每行两个整数 $l,r$。

输出格式

输出 $m$ 行，每行一个整数，为对应区间的 gcd。

数据范围

$1\le n,m\le 1000$，$1\le a_i\le 10^9$，$1\le l\le r\le n$。

样例

5 3
24 36 48 12 60
1 3
2 4
1 5

输出：

12
12
12