Cho dãy số nguyên dương \(n\) phần tử. Ta có thể thực hiện các thao tác sau với không giới hạn số lần:

• Chọn ra 2 số khác nhau bất kì trong dãy.
• Giảm giá trị số lớn đi một lượng bằng độ lớn số bé.

Yêu cầu:

• Hãy in ra tổng nhỏ nhất của dãy số sau một hoặc nhiều thao tác.

Input

• Dòng đầu ghi số \(n\) \((1 \leq n \leq 10^5)\)
• Dòng tiếp theo là \(n\) số nguyên \(a_i\) \((1 \leq a_i \leq 10^5)\)

Output

• In ra đáp án

Example

4
2 5 3 4

4

Cho số \(n\) và 1 dãy số \(a\) gồm \(m\) số, kiểm tra xem lần lượt mỗi số trong dãy \(a\) có phải là ước nguyên tố của \(n\) thì in ra YES, ngược lại in ra NO

Input

• 2 số nguyên \(n, m\) là độ dài dãy \(a\) \((1 \leq n \leq 10^5, 1 \leq m \leq 100)\)
• \(m\) dòng sau mỗi dòng một số nguyên thuộc dãy \(a\) \((1 \leq a_i \leq 10^5)\)

Output

• \(m\) dòng tương ứng với đáp án của từng số trong dãy

Example

12 5
1
2
3
4
5

NO
YES
YES
NO
NO

Nhập vào dãy \(a\) có \(n\) phần tử. Đếm xem trong dãy \(a\) có bao nhiêu số đặc biệt. Biết rằng số đặc biệt là số chia hết cho tổng các chữ số của chính số đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((n \leq 1000)\) là số lượng phần tử của dãy số.
• Dòng thứ hai chứa \(n\) số nguyên dương lần lượt là \(a_1, a_2, \ldots, a_n\) \((a_i \leq 10^6, 1 \leq i \leq n)\).

Output

• Gồm một dòng duy nhất chứa kết quả là số lượng số đặc biệt trong dãy \(a\).

Example

5
1 3 5 12 15

4

Là một người hướng đến sự hoàn hảo, bé Bon đặc biệt thích những thứ có sự đối xứng, vì thế bút của Bon có hẳn 2 đầu viết được (hoặc cả hai đầu đều không viết được :D).
Dạo gần đây, Bon biết được một thứ vô cùng mới mẻ là xâu palindrome (xâu đối xứng), bé Bon đã dành cả một buổi tối để tìm hiểu về nó và phát hiện ra không chỉ dãy ký tự, những dãy số cũng có thể là một dãy đối xứng.
Hãy giúp bé Bon kiểm tra xem nhưng dãy số mà bé Bon nghĩ ra có phải dãy đối xứng không.

Input

• Dòng 1 nhập \(N\) (\(1 \leq N \leq 3 * 10^4\)).
• Dòng 2 nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, |A_i| \leq 3 * 10^4\)).

Output

• Nếu dãy số bé Bon nghĩ ra là dãy đối xứng thì in ra YES, in ra NO nếu ngược lại.

Example

5
1 2 3 2 1

YES

5
1 2 3 4 5

NO

Cho dãy số gồm \(N\) phần tử. Giá trị tuyệt đối của các phần tử trong dãy không quá \(X\). Cần phải thêm ít nhất bao nhiêu số (\(\leq X\)) để tổng tất cả các phần tử bằng 0.

Input

• Dòng 1 nhập số nguyên dương \(N\) và \(X\) (\(1 \leq N \leq 10^5, 1 \leq X \leq 10^9\)).
• Dòng 2 nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, |A_i| \leq 10^9\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

3 2
-1 1 2

1