Một khối lớp 9 có \(A\) bạn nam và \(B\) bạn nữ. Thầy cô muốn chia cả khối thành các nhóm lao động sao cho số lượng nhóm là nhiều nhất có thể, nhưng phải đảm bảo hai điều kiện:

1. Số bạn nam trong mỗi nhóm phải bằng nhau.
2. Số bạn nữ trong mỗi nhóm phải bằng nhau.

Hãy xác định số nhóm lớn nhất có thể chia và số lượng bạn nam, bạn nữ trong mỗi nhóm đó.

Input

• Một dòng duy nhất chứa hai số nguyên dương \(A\) và \(B\) (\(1 \le A, B \le 10^9\)), lần lượt là tổng số học sinh nam và tổng số học sinh nữ.

Output

• Dòng đầu tiên in ra một số nguyên là số lượng nhóm lớn nhất có thể chia.
• Dòng thứ hai in ra hai số nguyên lần lượt là số học sinh nam và số học sinh nữ trong mỗi nhóm, cách nhau bởi một khoảng trắng.

Examples

24 18

6
4 3

35 27

1
35 27

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\).
Bạn được cho \(Q\) truy vấn, mỗi truy vấn là một số nguyên dương \(X\), hãy đếm số lượng các số trong dãy \(A\) mà chia hết cho \(X\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N \le 10^5\), \(1 \le Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^6\)).
• Dòng thứ ba chứa \(Q\) số nguyên dương \(X_1, X_2, \dots, X_Q\) (\(1 \le X_j \le 10^6\)) là các truy vấn.

Output

• Một dòng duy nhất in ra \(Q\) số nguyên, mỗi số là kết quả của một truy vấn tương ứng, cách nhau bởi một dấu cách.

Examples

5 3
12 5 24 6 15
2 3 7

3 4 0

4 2
100 200 100 50
10 100

4 3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 2000\) và \(Q \le 2000\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Một số nguyên tố là một số tự nhiên lớn hơn 1 và không có ước số dương nào khác ngoài 1 và chính nó.

Cho \(Q\) truy vấn, mỗi truy vấn là một số nguyên dương \(N\). Với mỗi truy vấn, bạn hãy xác định xem \(N\) có phải là số nguyên tố hay không.

Input

• Dòng đầu tiên chứa một số nguyên \(Q\) (\(1 \le Q \le 10^5\)) là số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(N\) (\(1 \le N \le 10^6\)) là số cần kiểm tra.

Output

• Gồm \(Q\) dòng, mỗi dòng in ra YES nếu số tương ứng là số nguyên tố, ngược lại in ra NO.

Examples

4
7
10
1
13

YES
NO
NO
YES

2
97
100

YES
NO

Một số nguyên tố là một số tự nhiên lớn hơn \(1\) và không có ước số dương nào khác ngoài \(1\) và chính nó.

Cho hai số nguyên dương \(L\) và \(R\). Nhiệm vụ của bạn là đếm xem có bao nhiêu số nguyên tố trong đoạn \([L, R]\) (tính cả \(L\) và \(R\)).

Input

• Một dòng duy nhất chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le 10^6\)).

Output

• In ra một số nguyên duy nhất là số lượng số nguyên tố trong đoạn \([L, R]\).

Examples

10 20

4

1 10

4