Cho hai số tự nhiên ~a~ và ~b~. Hãy tính xem ~2~ số này cách nhau bao nhiêu đơn vị.

Input

• Dòng thứ nhất chứa số tự nhiên ~a~ (~a \leq 1000~).
• Dòng thứ hai chứa số tự nhiên ~b~ (~b \leq 1000~).

Output

• In ra kết quả của bài toán.

Sample Test 1

Input:

10
4

Output:

6

Sample Test 2

Input:

1
3

Output:

2

Cho ba số tự nhiên ~a~, ~b~, ~c~. Hãy tìm số bé nhất trong ba số này.

Input

• Gồm một dòng chứa ba số tự nhiên ~a~, ~b~, ~c~ (~a, b, c \leq 1000~).

Output

• In ra kết quả của bài toán.

Sample Test 1

Input:

2 3 4

Output:

2

Sample Test 2

Input:

7 1 24

Output:

1

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 hai số nguyên ~L~ và ~R~. Hãy in ra giá trị tuyệt đối của các số nguyên từ ~L~ đến ~R~.

Input

• Gồm một dòng chứa hai số nguyên ~L, R~ (~-1000 \leq L \leq R \leq 1000~).

Output

• In ra giá trị tuyết đối của các số nguyên từ ~L~ đến ~R~ trên một dòng, các số cách nhau ~1~ khoảng trắng.

Sample Test 1

Input:

1 5

Output:

1 2 3 4 5

Sample Test 2

Input:

-4 3

Output:

4 3 2 1 0 1 2 3

Một số chính phương là bình phương (luỹ thừa bậc 2) của một số tự nhiên. Cho một số tự nhiên ~N~, hãy kiểm tra xem ~N~ có phải số chính phương hay không.

Input

• Gồm một số tự nhiên ~N~ duy nhất (~1 \leq N \leq 1000~).

Output

• In ra YES nếu ~N~ là số chính phương, ngược lại in ra NO.

Sample Test 1

Input:

9

Output:

YES

Sample Test 2

Input:

10

Output:

NO

Cho một hình chữ nhật có chiều dài, chiều rộng là các số tự nhiên với diện tích là ~S~. Hãy tính chu vi bé nhất có thể của hình chữ nhật đó.

Input

• Gồm một số tự nhiên ~S~ duy nhất (~1 \leq S \leq 10^6~).

Output

• In ra kết quả của bài toán.

Sample Test 1

Input:

10

Output:

14

Note: Trong các hình chữ nhật diện tích ~10~, hình chữ nhật kích thước ~2 \times 5~ có chu vi bé nhất.

Sample Test 2

Input:

7

Output:

16

Dino chọn tất cả các số tự nhiên từ ~a~ đến ~b~. Daisy chọn tất cả các số tự nhiên từ ~c~ đến ~d~. Hỏi hai bạn có chọn số nào giống nhau không?

Input

Gồm bốn dòng, mỗi dòng chứa lần lượt các số nguyên ~a~, ~b~, ~c~, ~d~. (~0 \leq a \leq b \leq 1000~, ~0 \leq c \leq d \leq 1000~)

Output

In ra YES nếu hai bạn chọn có số chung, ngược lại in ra NO.

Sample Test 1

Input:

5 
10 
15 
20

Output:

NO

Note:

• Dino chọn các số từ ~5~ đến ~10~: ~5, 6, 7, 8, 9, 10~
• Daisy chọn các số từ ~15~ đến ~20~: ~15, 16, 17, 18, 19, 20~
• Do các số hai bạn chọn không giống nhau nên kết quả là NO.

Sample Test 2

Input:

1 
4
2
6

Output:

YES

Note:

• Dino chọn các số từ ~1~ đến ~4~: ~1, 2, 3, 4~
• Daisy chọn các số từ ~2~ đến ~6~: ~2, 3, 4, 5, 6~
• Do các số hai bạn cùng chọn số ~2, 3, 4~ nên kết quả là YES.

Quá chán với việc xây dựng trang web lập trình, TDZ quyết định xây dựng một nhà mạng HNOJ mới để giúp coder dễ dàng trò chuyện, chia sẻ kinh nghiệm và chia sẻ code. Tuy nhiên, để duy trì nhà mạng HNOJ hoạt động thì cần phải có kinh phí, và TDZ quyết định sẽ bắt người dùng trả tiền để sử dụng dịch vụ.

Cụ thể, nhà mạng HNOJ quy định một tin nhắn cơ sở gồm 30 kí tự (sang kí tự thứ 31 sẽ tính đến tin nhắn thứ hai). Giá cước của mỗi tin nhắn cơ sở là 3 doge coin vì hiện tại lạm phát đang tăng cao.

Bây giờ, với mỗi một tin nhắn, bạn hãy tính thử xem bạn cần trả bao nhiêu doge coin cho nhà mạng HNOJ nhé.

Input

Gồm một xâu ~S~ khác rỗng có độ dài không quá 1000 ký tự thuộc bảng mã ASCII.

Output

In ra số doge coin cần trả dể gửi một tin nhắn ~S~ đó.

Sample Test 1

Input:

Hello, World!

Output:

3

Sample Test 2

Input:

Never gonna give you up. Never gonna let you down. Never gonna run around and desert you...

Output:

12

Để tiếp tục nâng cao trải nghiệm cho người dùng, nhà mạng HNOJ tiếp tục xây dựng dịch vụ kiểm tra số dư tài khoản chỉ với một nút gửi. Bạn vừa gửi yêu cầu kiểm tra tài khoản và nhận được thông báo, hãy tính số tin nhắn bạn còn có thể gửi được với số dư hiện tại, với chi phí cho mỗi tin nhắn cơ sở vẫn giữ là ~3~ dogecoin.

Input

Gồm một xâu có dạng:

So du tai khoan: x dogecoin

Với x là số dư hiện tại của người dùng (~x~ nguyên dương, ~|x| \leq 3000~).

Output

In ra số lượng tin nhắn cơ sở bạn có thể gửi được với số dư x.

Sample Test

Input:

So du tai khoan: 200 dogecoin

Output:

66

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

TDZ đang học về ước chung lớn nhất (~UCLN~). Nhưng khi nghe đến thứ gọi là "ước nguyên tố" thì TDZ đang rất mơ hồ vì cậu không nắm vững kiến thức về số nguyên tố. Vì vậy, TDZ nhờ bạn giải giúp bài tập này để thông não ra một tí:

Cho ~n~ số nguyên dương, hãy:

• Đếm số lượng số nguyên tố trong ~n~ số này.
• Tìm ~UCLN~ của ~n~ số này.

Input

• Dòng thứ nhất gồm một số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương có giá trị không vượt quá ~10^5~.

Output

• Dòng thứ nhất in ra số lượng số nguyên tố trong ~n~ số.
• Dòng thứ hai in ra ~UCLN~ của ~n~ số.

Subtasks

• Subtask ~1~ (~50\%~): Tất cả các số trong input nhỏ hơn ~10^3~.
• Subtask ~2~ (~50\%~): Không thay đổi.

Sample Test 1

Input:

5
3 6 2 9 5

Output:

3 
1

Note:

• Có ~3~ số nguyên tố là ~3, 2, 5~.
• ~UCLN(3, 6, 2, 9, 5) = 1~

Sample Test 2

Input:

4
4 8 10 6

Output:

0
2

Cho số nguyên dương ~N~.

Yêu cầu: Tính giá trị của:

Input

Một dòng duy nhất chứa số nguyên dương ~N \ (N \le 10^9)~.

Output

In ra kết quả cần tìm. Kết quả được coi là đúng nếu sai số không vượt quá ~10^{-18}~.

Sample Test

Input

5

Output

0.833333333333333333

Giải thích

~S = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \dfrac{1}{3 \times 4} + \dfrac{1}{4 \times 5} + \dfrac{1}{5 \times 6} = \dfrac{5}{6} = 0.8(3)~.

Cho ~n~ số nguyên dương. Hãy đưa ra ước chung lớn nhất của ~n~ số đó.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ (~n \leq 1000~).
• Dòng thứ hai chứa ~n~ số nguyên dương không vượt quá ~10^6~.

Output

In ra ước chung lớn nhất của ~n~ số.

Sample Test 1

Input:

4
2 4 6 8

Output:

2

Sample Test 2

Input:

4
1 2 4 5

Output:

1

Một cặp số sinh đôi là hai số nguyên tố có khoảng cách là 2 đơn vị. Cho một số nguyên dương ~n~, hãy đưa ra số lượng các cặp số sinh đôi khác nhau mà các số đều không vượt quá ~n~.

Hai cặp số sinh đôi được gọi là khác nhau nếu chúng không phải hoán vị của nhau, hay nói cách khác tồn tại ít nhất một số chỉ thuộc một cặp duy nhất. Ví dụ:

• ~(3, 5)~, ~(5, 7)~ là hai cặp số sinh đôi khác nhau.
• ~(3, 5)~, ~(5, 3)~ không là hai cặp số sinh đôi khác nhau.

Input

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

Output

In ra số lượng các cặp số sinh đôi theo yêu cầu đề bài.

Sample Test

Input:

7

Output:

2

Note:

• Hai cặp số thoả mãn là ~(3, 5)~ và ~(5, 7)~.

Cho một số nguyên dương chẵn ~n~. Hãy liệt kê tất cả các cách phân tích ~n~ thành tổng của hai số ~a~ và ~b~ sao cho: ~ \begin{cases} a \leq b\\ a, b \text{ nguyên tố} \\ a + b = n \end{cases} ~

Input

Gồm một số nguyên dương chẵn ~n~ duy nhất (~n \leq 1000~).

Output

• Dòng thứ nhất chứa số ~k~ - số lượng cách phân tích khác nhau.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số ~a~ và ~b~ thoả mãn yêu cầu đề bài. Các cặp số ~(a, b)~ có thể được in theo thứ tự bất kì.

Sample Test 1

Input:

10

Output:

2
3 7
5 5

Sample Test 2

Input:

18

Output:

2
7 11
5 13

Cho một xâu ~S~, hãy đếm số lần xuất hiện của các chữ số ~0~, ~1~, ~2~,..., ~9~ trong xâu ~S~.

Input

Gồm một xâu ~S~ duy nhất chứa các ký tự là chữ cái và chữ số, độ dài không quá ~100~ ký tự.

Output

Gồm 10 dòng, dòng thứ ~i~ in ra số lượng chữ số (~i - 1~) xuất hiện trong dãy ~S~.

Sample Test

Input:

a1bc321

Output:

0
2
1
1
0
0
0
0
0
0

Cho một xâu kí tự ~S~. Hãy liệt kê tất cả các từ trong xâu ~S~ trên các dòng khác nhau (Mỗi từ là một dãy kí tự khác kí tự trắng liên tiếp nhau).

Input

Gồm một xâu kí tự ~S~ duy nhất có độ dài không vượt quá ~1000~ ký tự.

Output

• Dòng đầu tiên in ra số ~k~ - số lượng từ trong xâu ~S~.
• ~k~ dòng tiếp theo, mỗi dòng lần lượt in ra các từ trong xâu ~S~ theo thứ tự xuất hiện của chúng.

Sample Test

Input:

abc cba ddd

Output:

3
abc
cba
ddd

Một đoạn văn bản hoàn chỉnh là đoạn văn bản không có kí tự trắng (dấu cách) dư thừa:

• Không có dấu cách ở đầu đoạn.
• Giữa các từ chỉ tồn tại một kí tự trắng.

Cho một dãy các ký tự ~S~, hãy đưa ra dãy ~S~ sau khi được sửa thành đoạn văn bản hoàn chỉnh.

Input

Gồm một dãy ~S~ chỉ chứa các kí tự trắng hoặc các chữ cái Tiếng Anh (~|S| \leq 1000~).

Output

In ra ~S~ là đoạn văn bản hoàn chỉnh.

Sample Test

Input:

   Ha Noi    Online      Judge

Output:

Ha Noi Online Judge

Dữ liệu đảm bảo để bài luôn có kết quả!

Xét hai số nguyên dương ~u, v~, ta gọi thao tác ghép hai số ~u, v~ là thao tác viết số ~v~ sau số ~u~.

Ví dụ: Với ~u = 123, v = 456~, sau khi ta ghép hai số ~u, v~ với nhau, ta được số ~123456~.

Cho ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Hãy cho biết: Có bao nhiêu cặp chỉ số ~(i, j) \ (1 \le i \lt j \le n)~ sao cho khi ta thực hiện thao tác ghép hai số ~a_i, a_j~, ta được một số mới chia hết cho ~3~?

Input

• Dòng đầu tiên chứa số nguyên dương ~n \ (n \ge 2);~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n.~

Output

In ra kết quả là số cặp chỉ số ~(i, j)~ thoả mãn đề bài.

Scoring

• Subtask 1 [20%]: ~n \le 1000; \ a_i \le 10^9;~
• Subtask 2 [40%]: ~n \le 10^5; \ a_i \le 10^{18};~
• Subtask 3 [40%]: ~n \le 10^5; \ a_i \le 10^{100}.~

Examples

Input

7
123 4 5 7 10 3 2

Output

7

Giải thích: Các cặp chỉ số thoả mãn yêu cầu đề bài là: ~(1, 6), (2, 3), (2, 7), (3, 4), (3, 5), (4, 7), (5, 7).~

Cho dãy số nguyên ~a = (a_1, a_2, ..., a_n)~ bạn được thay số ~0~ trong ~a~ bởi một số nguyên bất kỳ khác sau đó chọn ra trong dãy ~a~ một số nhiều nhất các số (không cần đúng thứ tự) sao cho các số đã chọn tạo thành một dãy số nguyên liên tiếp.

Yêu cầu: Tìm cách có được dãy số nguyên liên tiếp dài nhất theo cách trên.

Ví dụ với ~a = (1, 0 ,3 ,8 ,5 ,9 ,0)~, ta có thể thay hai số ~0~ lần lượt bởi ~6~ và ~7~, khi đó có thể chọn trong ~a~ ra các số ~(5, 6, 7, 8, 9)~ để được dãy số nguyên liên tiếp dài nhất.

INPUT

Dòng 1 chứa số nguyên dương ~n \le 10^6~

Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (giá trị ~i~: ~|a_i| \le 10^6~)

OUTPUT

Số nguyên duy nhất là độ dài dãy số nguyên liên tiếp thu được theo phương án của bạn.

SAMPLE INPUT

7
1 0 3 8 5 9 0

SAMPLE OUTPUT

5

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

Trong phòng thí nghiệm chỉ có đúng ba loại cốc có dung tích là ~5 \ (ml)~, ~3 \ (ml)~ và ~2 \ (ml)~. Hỏi cần ít nhất bao nhiêu lần đong nước để lấy được đúng ~N \ (ml)~.

Dữ liệu:

Một số nguyên dương duy nhất ~N~ ~(2 \le N \le 10^{18})~ là số nước cần đong.

Kết quả:

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

Ví dụ

Input

12

Output

3

Giải thích

Đong hai lần bằng cốc ~5 \ (ml)~ và một lần bằng cốc ~2 \ (ml)~.

Input

6

Output

2

Giải thích

Đong hai lần bằng cốc ~3 \ (ml)~.

Cho một dãy số gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ có giá trị không vượt quá ~10^6~. Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Dữ liệu:

• Dòng đầu tiên gồm một số nguyên dương ~N \ (N \le 10^6)~ là số lượng phần tử của dãy số;
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ lần lượt mô tả các phần tử của dãy số.

Kết quả:

Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra ~-1~.

Ví dụ

Input

10
3 4 8 4 5 6 1 7 4 6

Output

4

Giải thích

Chọn dãy con từ vị trí thứ ~5~ đến vị trí thứ ~8~: ~5, 6, 1, 7~.

Ràng buộc

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

Cho bốn số thực ~𝐴, 𝐵, 𝐶, 𝐷~. Hỏi tích của bốn số đó là số dương, số âm hay số ~0~.

Dữ liệu:

Gồm bốn dòng, mỗi dòng gồm một số thực lần lượt là bốn số ~𝐴, 𝐵, 𝐶, 𝐷~ ~(-10^{18} ≤ 𝐴, 𝐵, 𝐶, 𝐷 ≤ 10^{18})~.

Kết quả:

Một số nguyên duy nhất là:

• ~1~ nếu tích bốn số là số dương~;~
• ~-1~ nếu tích bốn số là số âm~;~
• ~0~ nếu tích bốn số là số ~0.~

Ví dụ

Input

20.21
-1.2
-2.3
1.0

Output

1

Input

5.0
-8.9
0.0
123.456

Output

0

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

Dữ liệu:

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

Kết quả:

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

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

Ví dụ

Input

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.