---
# System prepended metadata

title: 'Đề: Đốn cây'

---

# Đốn cây

Một lão tiều phu tên Mely vào rừng đốn cây. Một hôm lão quyết định sẽ đốn tất cả các cây trên hàng cây có $N$ cây, cây thứ $i$ có độ cao $a_i$. Lão là một người bị rối loạn ám ảnh cưỡng chế, nên tất cả các khúc cây đốn về phải có độ dài là các số nguyên bằng nhau và không có một khúc gỗ thừa nào. Tuy nhiên vì phát hiện cây còn chưa đủ cao, nên lão quyết định chờ cho cây đủ lớn sẽ đốn sau. Giả định rằng cứ mỗi một ngày trôi qua, mỗi cây sẽ cao thêm $1$. Lão hỏi bạn nếu $k$ ngày sau lão đốn cây, độ dài lớn nhất của $1$ khúc cây có thể đốn là bao nhiêu.

### Input

- Dòng thứ nhất gồm hai số nguyên dương $N,Q$ $(1 \le N,Q \le 2\cdot 10^5)$ là số lượng cây và số lượng truy vấn.
- Dòng thứ hai gồm $N$ số nguyên dương $a_1, a_2,...,a_n$ $(0\le a_i \le 10^9)$ là độ cao của cây.
- $Q$ dòng tiếp theo, mỗi dòng gồm một số nguyên dương $k$.
### Output.
Với mỗi giá trị $k$, in ra màn hình độ dài lớn nhất của mỗi khúc cây nếu đốn cây sau $k$ ngày.

#### Sample input
```
5 3
5 13 9 5 1
2
1
3
```
#### Sample output
```
1 
2
4
```

Giải thích: 
- Với $k = 1$, độ dài của cây sau $1$ ngày là $[6,14,10,6,2]$, và độ dài lớn nhất của mỗi khúc cây là $2$.
- Với $k = 3$, độ dài của cây sau $3$ ngày là $[8,16,12,8,4]$, và độ dài lớn nhất của mỗi khúc cây là $4$.

## Lời giải:

Nói cách khác, để độ dài $x$ của một khúc cây đốn về là một số nguyên, không bỏ sót một khúc gỗ nào và x lớn nhất có thể, thì $x$ phải là ước chung lớn nhất của dãy: $[a_1+k,a_2+k,...,a_n+k]$.

Với giới hạn dữ liệu $N,Q\le2\cdot10^5$, buộc phải có một cách tiền xử lý và thực hiện truy vấn trong khoảng $O(1)$ hoặc $O(logN)$.

Để ý đến tính chất: $gcd(a,b) = gcd(a,abs(a-b))$. Như vậy thì $gcd(a_1+k,a_2+k) = gcd(a_1+k,abs(a_1-a_2))$.
Áp dụng tính chất trên với cả mảng:
$gcd(a_1+k,a_2+k,..., a_n+k) = gcd(a_1+k,abs(a_1-a_2),..., abs(a_1-a_n))$

Như vậy chỉ với việc tính toán trước giá trị của $A = gcd(abs(a_1-a_2),...,abs(a_1-a_n)).$ Có thể dễ dàng tính toán giá trị cần tìm là $gcd(a_1+k,A)$.