Cho một xâu ký tự chỉ gồm các chữ cái tiếng Anh và khoảng trắng.
Hãy đếm xem trong xâu có bao nhiêu chữ cái khác nhau (không phân biệt chữ hoa, chữ thường).

• Input:
  • Dòng 1: xâu ký tự S (có thể chứa khoảng trắng, độ dài ≤ 255).
• Output:
  • Một số nguyên: số lượng chữ cái khác nhau xuất hiện trong S.

Ví dụ

Input 1

Hello World

Output 1

7

Giải thích: các chữ cái khác nhau (không phân biệt hoa thường) là: h, e, l, o, w, r, d.

Input 2

AAA bbb CCC

Output 2

3

Cho dãy số nguyên gồm N phần tử. Hãy tìm tổng lớn nhất của một đoạn con liên tiếp trong dãy.

• Input:
  • Dòng 1: số nguyên N (1 ≤ N ≤ 10^5).
  • Dòng 2: N số nguyên a[i] (|a[i]| ≤ 10^4).
• Output:
  • Một số nguyên: tổng lớn nhất của một đoạn con.

Ví dụ

Input 1

5
1 -2 3 4 -1

Output 1

7

Đoạn con có tổng lớn nhất là 3 4.

Input 2

4
-5 -2 -3 -4

Output 2

-2

Cho một số nguyên dương N (có thể rất lớn, lên đến 1000 chữ số), được cho dưới dạng xâu.
Hãy tính:

1. Tổng các chữ số của N.
2. Số chữ số chẵn của N.
3. Số chữ số lẻ của N.

• Input:
  • Dòng 1: xâu ký tự biểu diễn số nguyên dương N (không có dấu +/-).
• Output:
  • Ba số nguyên cách nhau một khoảng trắng: tổng chữ số, số chữ số chẵn, số chữ số lẻ.

Ví dụ

Input

120345

Output

15 3 3

Trong một buổi thi Tin học, có N học sinh, mỗi em có một chiều cao.
Giám thị cần xếp các em đứng thành một hàng sao cho chiều cao không giảm dần từ trái sang phải.

Hãy in ra dãy chiều cao sau khi sắp xếp.

• Input:
  • Dòng 1: số nguyên N (1 ≤ N ≤ 10^5).
  • Dòng 2: N số nguyên h[i] (1 ≤ h[i] ≤ 2*10^9).
• Output:
  • Một dòng gồm N số, là dãy h[i] sau khi sắp xếp tăng dần.

Ví dụ

Input

5
150 160 155 145 160

Output

145 150 155 160 160

Cho một xâu S biểu diễn họ tên, có thể có nhiều khoảng trắng thừa (đầu, cuối, hoặc nhiều khoảng trắng giữa các từ), chữ cái có thể lẫn lộn hoa/thường.

Hãy chuẩn hóa họ tên theo quy tắc:

• Xóa khoảng trắng ở đầu và cuối xâu.
• Giữa các từ chỉ để một khoảng trắng.
• Chữ cái đầu mỗi từ viết hoa, các chữ cái còn lại viết thường.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 255).
• Output:
  • Một dòng duy nhất là xâu đã chuẩn hóa.

Ví dụ

Input

   nGuyeN   tHe   quYEt  

Output

Nguyen The Quyet

Cho dãy N số nguyên. Hãy tìm độ dài lớn nhất của một đoạn con liên tiếp có các phần tử tăng dần nghiêm ngặt.

• Input:
  • Dòng 1: số nguyên N (1 ≤ N ≤ 10^5).
  • Dòng 2: N số nguyên a[i] (|a[i]| ≤ 10^9).
• Output:
  • Một số nguyên: độ dài lớn nhất của đoạn con tăng dần.

Ví dụ

Input

7
1 2 2 3 4 1 2

Output

3

Giải thích: đoạn 2 3 4 có độ dài 3 là lớn nhất.

Một mật khẩu được coi là mạnh nếu thỏa mãn cả 4 điều kiện:

1. Độ dài từ 8 đến 20 ký tự.
2. Có ít nhất một chữ cái viết hoa.
3. Có ít nhất một chữ cái viết thường.
4. Có ít nhất một chữ số.

Cho xâu S, hãy kiểm tra xem đó có phải mật khẩu mạnh không.

• Input:
  • Dòng 1: xâu S (không có khoảng trắng, chỉ gồm chữ cái tiếng Anh và chữ số).
• Output:
  • In YES nếu S là mật khẩu mạnh, ngược lại in NO.

Ví dụ

Input 1

abcD1234

Output 1

YES

Input 2

abc123

Output 2

NO

Có N gói quà, gói thứ i có khối lượng a[i].
Một chiếc hộp có thể chứa tối đa khối lượng M.
Hãy xếp tất cả các gói quà vào ít hộp nhất, biết rằng mỗi hộp có thể chứa tối đa 2 gói quà.

Yêu cầu: In ra số lượng hộp ít nhất cần dùng.

• Input:
  • Dòng 1: N, M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^9).
  • Dòng 2: N số nguyên a[i] (1 ≤ a[i] ≤ M).
• Output:
  • Một số nguyên: số hộp ít nhất.

Ví dụ

Input

5 10
3 5 3 9 4

Output

3

Cho một xâu S gồm nhiều từ, các từ cách nhau bởi một hoặc nhiều dấu cách.
Hãy đếm xem trong S có bao nhiêu từ khác nhau, không phân biệt chữ hoa và chữ thường.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 255).
• Output:
  • Một số nguyên: số từ khác nhau trong S.

Ví dụ

Input

Nguyen the Quyet   nguyen   The   quyet

Output

3

Cho một xâu S gồm các từ cách nhau bởi một hoặc nhiều dấu cách.
Hãy in ra độ dài của từ dài nhất trong S.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 255).
• Output:
  • Một số nguyên: độ dài từ dài nhất.

Ví dụ

Input

Hoc lap trinh Cplusplus that thu vi

Output

9

Giải thích: từ dài nhất là Cplusplus có 9 ký tự.

Cho hai xâu S và T.
Hãy xóa tất cả các lần xuất hiện của T trong S. Sau khi xóa, in ra xâu S mới.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 1000).
  • Dòng 2: xâu T (độ dài ≤ |S|, T khác rỗng).
• Output:
  • Một dòng là xâu S sau khi xóa hết T.

Ví dụ 1

Input

ababab
ab

Output

(xâu rỗng, không có ký tự nào)

Ví dụ 2

Input

laptrinhCpluspluslaptrinh
laptrinh

Output

Cplusplus

Cho một xâu S chỉ gồm các chữ cái tiếng Anh (hoa hoặc thường) và số nguyên dương K.
Hãy mã hóa S bằng cách dịch chuyển mỗi chữ cái sang phải K vị trí trong bảng chữ cái vòng tròn:

• Với chữ thường: a → b → … → z → a.
• Với chữ hoa: A → B → … → Z → A.

• Các ký tự không phải chữ cái (nếu có) giữ nguyên.

• Input:

  • Dòng 1: xâu S (độ dài ≤ 255).
  • Dòng 2: số nguyên K (1 ≤ K ≤ 10^9).
• Output:
  • Một dòng là xâu sau khi mã hóa.

Ví dụ

Input

AbZz
3

Output

DeCc

Giải thích:

• A → D, b → e, Z → C, z → c.

Cho hai số nguyên không âm A và B, mỗi số có thể có tới 1000 chữ số.
Hãy tính A + B và in kết quả.

• Input:
  • Dòng 1: xâu A.
  • Dòng 2: xâu B.
• Output:
  • Một dòng là A + B (không có số 0 thừa ở đầu).

Ví dụ

Input

12345678901234567890
9876543210

Output

12345688777777780100

Cho một đoạn văn bản gồm nhiều từ, các từ chỉ gồm chữ cái tiếng Anh và được phân cách bằng một hoặc nhiều dấu cách.
Hãy thống kê tần suất xuất hiện của mỗi từ (không phân biệt chữ hoa, chữ thường) và in ra theo thứ tự từ điển tăng dần.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 1000).
• Output:
  • Mỗi dòng gồm: từ, một khoảng trắng, rồi đến số lần xuất hiện.
  • Các từ in theo thứ tự từ điển tăng dần (a → z).

Ví dụ

Input

Hoc lap trinh hoc lap trinh Cplusplus

Output

cplusplus 1
hoc 2
lap 2
trinh 2

Tuấn là một học sinh yêu thích Tin học. Gần đây, Tuấn nghe nói về sức mạnh của robot thông minh ChatGPT nên đã đố ChatGPT một bài toán như sau:

Cho số nguyên dương n. Tìm số lượng các số nguyên dương X nhỏ hơn n thỏa mãn: X và n là hai số nguyên tố cùng nhau (tức là Ước chung lớn nhất của X và n bằng 1).

Thật thú vị, khi Tuấn nhập ~n = 5~, ChatGPT đưa ra kết quả là: Có 4 số, cụ thể là các số 1, 2, 3, 4.

Yêu cầu: Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT với các số n lớn hơn nhé!

Dữ liệu vào (Input): Nhập từ bàn phím một số nguyên dương n ~(2 \le n \le 2 \times 10^9)~.

Kết quả ra (Output): In ra màn hình một số nguyên duy nhất là số lượng các số nguyên dương X nhỏ hơn n và nguyên tố cùng nhau với n.

Giới hạn:

• Có 50% số điểm: ~2 \le n \le 2000~
• Có 40% số điểm: ~2000 < n \le 2 \times 10^6~
• Có 10% số điểm: ~2 \times 10^6 < n \le 2 \times 10^9~

Ví dụ:

Trong buổi ôn tập cho đội tuyển dự thi học sinh giỏi, thầy giáo đã ra cho bạn An một bài tập về số học như sau: Cho số nguyên dương n. Hãy tính xem, trong các ước của n có bao nhiêu ước là số nguyên tố? Bạn An đã dễ dàng đưa ra kết quả đúng của bài toán.

Yêu cầu: Hãy viết chương trình đưa ra kết quả mà bạn An tìm được.

Dữ liệu vào (Input): Nhập từ bàn phím một số nguyên dương n (~2 \le n \le 10^{12}~).

Kết quả ra (Output): In ra màn hình một số nguyên duy nhất là số lượng các ước của n là số nguyên tố.

Giới hạn:

• Có 60% số test ứng với 60% số điểm thoả mãn: ~2 \le n \le 10^3~
• Có 20% số test ứng với 20% số điểm thoả mãn: ~10^3 < n \le 10^6~
• Có 20% số test ứng với 20% số điểm thoả mãn: ~10^6 < n \le 10^{12}~

Ví dụ:

Input:

10

Output:

2

Giải thích:

n=10 có 4 ước là: 1, 2, 5, 10. Trong đó có 2 ước là số nguyên tố là 2 và 5.