Bạn có một dãy số gồm \(n\) số nguyên dương \(a_1,a_2,a_3,\ldots,a_n\) và số nguyên dương \(k\).

Bạn sẽ làm thao tác này tối đa \(k\) lần:

• Chọn \(i \ \in [1;n]\) và cộng \(1\) vào \(a_i\). \(( * )\)

Bạn cần làm theo thao tác \(( * )\) sao cho \(gcd(a_1,a_2,\ldots,a_n)\) đạt giá trị lớn nhất có thể. Lưu ý rằng bạn có thể làm thao tác đó ít hơn hoặc bằng \(k\) lần (bạn có thể không cần làm theo và tính luôn).

Biết rằng \(gcd(a,b)\) là ước chung lớn nhất của \(a\) và \(b\).

Yêu Cầu: Bạn hãy lập chương trình giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n,k\) \((2\ \le n\ \le3\times{10}^5, 1\ \le k\ \le\ {10}^{18})\).
• Dòng còn lại chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((1\ \le a_i\ \le\ 3\times{10}^5)\), mỗi số cách nhau một khoảng trắng

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(2 \le n \le 5\) và \(1 \le k \le 2 \times n\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 6
3 4 9

5

3 4
30 10 20

10