題目描述

對于兩個正整數?a,b，他們的最大公因數記為?gcd(a,b)。對于?k>3?個正整數?c1?,c2?,…,ck?，他們的最大公因數為：

gcd(c1?,c2?,…,ck?)=gcd(gcd(c1?,c2?,…,ck?1?),ck?)

給定?n?個正整數?a1?,a2?,…,an??以及?q?組詢問。對于第?i(1≤i≤q)?組詢問，請求出?a1?+i,a2?+i,…,an?+i?的最大公因數，也即?gcd(a1?+i,a2?+i,…,an?+i)。

輸入格式

第一行，兩個正整數?n,q，分別表示給定正整數的數量，以及詢問組數。

第二行，n?個正整數?a1?,a2?,…,an?。

輸出格式

輸出共?q?行，第?i?行包含一個正整數，表示?a1?+i,a2?+i,…,an?+i?的最大公因數。

輸入輸出樣例

輸入?

5 3
6 9 12 18 30

輸出?

1
1
3

輸入?

3 5
31 47 59

輸出?

4
1
2
1
4

說明/提示

對于?60%?的測試點，保證?1≤n≤103，1≤q≤10。

對于所有測試點，保證?1≤n≤105，1≤q≤105，1≤ai?≤1000。