Cho một số tự nhiên ~n~. Tính tổng ~1 + 2 + 3 + ... + n~.

Input

Gồm một số ~n~ duy nhất. (~n \leq 3 \times 10^5~)

Output

In ra tổng cần tìm.

Sample Test

Input:

5

Output:

15

Cho một số tự nhiên ~N~. Hãy in ra cụm từ tdz ~N~ lần, các cụm cách nhau bởi một dấu cách.

Input

Một số tự nhiên ~N~ duy nhất. (~N \leq 10^5~)

Output

Một dòng gồm toàn cụm tdz theo yêu cầu đề bài.

Sample Test

Input:

3

Output:

tdz tdz tdz

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

Hãy viết chương trình nhập một xâu và viết xâu đó theo chiều dọc.

Input

Gồm một xâu S duy nhất. Độ dài xâu S không vượt quá ~1000~ và xâu S không bao gồm dấu cách.

Output

In ra các ký tự của xâu S lần lượt trên các dòng khác nhau.

Sample Input

Input:

Hello

Output:

H
e
l
l
o

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

Tên tệp của một file Python bắt buộc gồm hai phần, ngăn cách bởi một dấu chấm .:

• Phần tên: Là một xâu không rỗng, gồm các kí tự từ a đến z, A đến Z, 0 đến 9, dấu gạch dưới (_) hoặc dấu gạch ngang (-).
• Phần mở rộng: Là xâu py, không phân biệt chữ hoa chữ thường.

Ví dụ:

• Tên file Python hợp lệ: a.py, Hello-world.py, tXz_69420.Py.
• Tên file Python không hợp lệ: among us.py (chứa dấu cách), 6/9/2022.py (chứa dấu /), pa064.cpp (sai phần mở rộng).

Bạn được cho một xâu, hãy kiểm tra xem xâu đó liệu có thể là tên hợp lệ cho một file Python không nhé.

Input

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

Output

In ra YES nếu S là tên file Python hợp lệ, ngược lại in ra NO.

Sample Test 1:

Input:

helloWorld.py

Output:

YES

Sample Test 2:

Input:

pythonIntro.docx

Output:

NO

Sample Test 3:

Input:

test_ko_sai_nhe_hehe.py

Output:

YES

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