Cho số nguyên dương ~n~, hãy phân tích ~n~ thành tích các thừa số nguyên tố và in ra chúng.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~2 \leq n \leq 10^9~)

Output

Gồm một dòng chứa các thừa số nguyên tố theo thứ tự từ bé đến lớn, mỗi số cách nhau một dấu cách.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 10^5~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test

Input:

60

Output:

2 2 3 5

Cho số nguyên dương ~n~, hãy kiểm tra xem ~n~ có phải là số nguyên tố hay không.

Input

Gồm một số nguyên ~n~ duy nhất (~n \leq 10^9~)

Output

In ra YES nếu ~n~ là số nguyên tố, ngược lại thì in ra NO.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 10^3~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test

Input:

3

Output:

YES

Cho số nguyên dương ~k~, hãy liệt kê tất cả số nguyên tố từ ~1~ đến ~k~.

Input

Gồm một số nguyên dương ~k~ duy nhất. (~1 < k \leq 10^5~)

Output

Gồm nhiều dòng, mỗi dòng lần lượt chứa một số nguyên tố trong khoảng ~[1, k]~. Các số được in theo thứ tự từ bé đến lớn.

Sample Test 1

Input:

3

Output:

2
3

Sample Test 2

Input:

14

Output:

2 
3 
5 
7 
11
13

Cho hai số nguyên dương ~a~ và ~b~. Hãy tìm ước chung lớn nhất và bội chung nhỏ nhất của hai số đó.

Input

Gồm một dòng chứa hai số nguyên dương ~a~ và ~b~. (~a, b \leq 10^6~)

Output

Gồm hai dòng, dòng đầu tiên chứa ước chung lớn nhất và dòng thứ hai chứa bội chung nhỏ nhất của ~a~ và ~b~.

Sample Test

Input:

2
5

Output

1
10

Cho số nguyên dương ~n~. Kiểm tra xem ~n~ có phải là số đối xứng hay không.

Các số đối xứng là các số không thay đổi khi viết theo thứ tự từ trái sang phải hoặc từ phải sang trái.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 10^{18}~)

Output

In ra YES nếu ~n~ là số đối xứng, ngược lại in ra NO.

Sample Test 1

Input:

123

Output:

NO

Sample Test 2

Input:

121

Output:

YES

Cho một số nguyên dương ~n~. Hãy liệt kê tất cả số nguyên tố nhỏ hơn hoặc bằng ~n~.

Input

Gồm một số nguyên dương ~n~ duy nhất (~2 \leq n \leq 10^5~).

Output

In ra tất cả các số nguyên tố không vượt quá ~n~ theo thứ tự tăng dần trên cùng một dòng.

Sample Test

Input:

14

Output:

2 3 5 7 11 13

Cho hai xâu ~S~ và ~T~, hãy kiểm tra xem ~T~ có phải là một xâu con liên tiếp của ~S~ hay không.

Input

Gồm hai dòng, dòng thứ nhất chứa xâu ~S~ và dòng thứ hai chứa xâu ~T~. Độ dài các xâu không vượt quá 100 ký tự.

Output

In ra YES nếu ~T~ là xâu con liên tiếp của ~S~, ngược lại in ra NO.

Sample Test

Input:

abba
ab

Output:

YES

Cho ba số nguyên dương ~a,b,c~. Tìm số lớn thứ hai trong ba số đó. Biết số lớn thứ hai là số lớn hơn đúng một số trong hai số còn lại.

Input:

Gồm ba dòng, mỗi dòng chứa một số nguyên dương lần lượt là ba số ~a,b,c~ ~(a,b,c≤10^9)~.

Output:

Một số nguyên duy nhất là số lớn thứ hai trong ba số đã cho. Nếu không có số thoả mãn thì in ra ~-1~.

Sample Test 1

Input:

3
9
5

Output

5

Sample Test 2

Input:

6
6
6

Output

-1

Cho một số nguyên dương ~N~. Đếm xem có bao nhiêu số nguyên không âm nhỏ hơn ~N~ và có tận cùng là chữ số ~K~.

Input:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N≤10^9)~.
• Dòng thứ hai chứa số nguyên ~K~ ~(0≤K≤9)~.

Output:

Một số nguyên duy nhất là số lượng số thoả mãn yêu cầu đề bài.

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn: ~N≤10^6~;
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Sample Test

Input:

68
3

Output

7

Giải thích

Các số thoả mãn là: ~3,13,23,33,43,53,63~.

Cho hai xâu kí tự ~X,Y~ gồm các kí tự chữ thường. Kiểm tra xem hai xâu có phải là anagram của nhau hay ko? Hai xâu là anagram của nhau nếu hoán vị của xâu này sẽ là xâu kia.

Input

Gồm hai dòng, mỗi dòng gồm một xâu kí tự (có độ dài không quá ~10^5~ kí tự).

Output

Nếu hai xâu là anagram của nhau thì ghi ra YES, ngược lại thì ghi NO.

Sample Test 1

Input:

dear
read

Output

YES

Sample Test 2

Input:

dead
dae

Output

NO

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

9
1 3 -1 3 -2 4 -5 -6 7

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

9
1 3 -1 3 -2 4 -5 6 7

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6