1282 . 愛蜜利雅的作業2
TopCoder
Description
這一天 羅茲瓦爾 為了 讓愛蜜莉雅更接近王，於是 丟了一道問題給她，可是愛蜜莉雅發現自己好像做不 出來 ，於是她想請你幫忙解決這個問題。
問題如下 :
「程序題 :給定一個 給定一個$N$項正整數序列，有$Q$次操作 ， 每次操作有兩種type，type 1 將區間每個元素都 將區間每個元素都加上一個正整數$k$，type 2輸出一個區間中所有數字的最大公因數」
愛蜜莉亞知道你是程式高手，希望能幫忙解決 這個問題，若你能解出來說不定就看到她那燦爛的笑容喔(maybe就像以下這樣 ) (謎之音 :我想看我想看 > /// < 看我速把這題AC掉吧XD )。
Input Format
第一行 有兩個正整數$N$、$Q$，分別代表這個正整數列的項數，及詢問次數。
接下來一行有$N$個正整數，代表該數列每一項的數字。
接下來$Q$行，每行以1或2開頭 :
若以1開頭 ，隨後會有三個正整數$ l , r, k$($1\leq l\leq r\leq N$)，此操作為將區間$[l , r]$中每個數字加上$k$
若以2開頭，隨後會有兩個正整數$l , r$($1\leq l\leq r\leq N$)，此操作為詢問，請輸出區間 $[l , r]$中所有數字的最大公因數。
保證過程中數列的每個數字皆小於等於$2^ {62}$
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $1\leq N\leq 10^ 3, 1\leq Q \leq 10^ 3$ | 5 |
| 2 (5~9) | $1\leq N\leq 10^ 5, 1\leq Q\leq 10^ 5$，無type 1的操作 | 10 |
| 3 (10~14) | $1\leq N \leq 10^ 5,1\leq Q \leq 10^ 5$，若操作為type 1，則$l=r$ | 15 |
| 4 (15~19) | $1\leq N \leq 10^ 5,1\leq Q \leq 10^ 5$ | 70 |
Output Format
對於每個詢問操作，輸出該的區間所有元素 的最大公因數。
Sample Input 1
5 1
1 2 3 4 5
2 1 5
1 2 3 4 5
2 1 5
Sample Output 1
1
Hints
Problem Source
Problem and Description by 殿仁．王
Set by Paupière
建國中學105學年度校內第三次模擬賽pB
題目取自2016年附中資訊校內賽Task 7
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 5 |
| 2 | 5~9 | 10 |
| 3 | 10~14 | 15 |
| 4 | 15~19 | 70 |