数列の区間におけるGCD（最大公約数）

n 個の整数が与えられたとき、q 個のクエリに答える必要があります。各クエリは、「インデックス l から r の間にあるすべての数の最大公約数（GCD）はいくつか？」という内容です。

入力

最初の行には、2 つの整数 n (1 ≤ n ≤ 5000) と q (1 ≤ q ≤ 10) が与えられます。

次の行では、空白区切りで n 個の整数が入力され、これは配列 (1 ≤ ≤ ) を表します。

続いて、q 行それぞれに、クエリ範囲を示す 2 つの数が与えられます (0 ≤ ≤ < n)。

出力

インデックス l から r まで（両端を含む）にあるすべての数の最大公約数を出力してください。

例