Minh cho rằng độ đẹp của một số tự nhiên chính là tổng các ước tự nhiên lẻ của số đó. Ví dụ số ~10~ có hai ước lẻ là ~1~ và ~5~ nên độ đẹp của ~10~ là ~1 + 5 = 6~.

Yêu cầu

Cho một số tự nhiên ~n~, em hãy giúp Minh tính độ đẹp của ~n~ nhé!

Dữ liệu vào

Gồm một số tự nhiên ~n~ ~(1 \le n \le 10^{14})~.

Kết quả

Gồm một số nguyên duy nhất là độ đẹp của ~n~.

Ràng buộc dữ liệu

• Có 60% test có ~1 \le n \le 10^6~.
• Có 40% test có ~10^6 < n \le 10^{14}~.

Ví dụ

Ví dụ 1

INPUT

4

OUTPUT

1

Ví dụ 2

INPUT

1234

OUTPUT

618

Số chính phương là số có thể viết dưới dạng bình phương của một số tự nhiên.

Ví dụ: ~1, 4, 49~ là các số chính phương còn ~2, 5, 20~ không phải là số chính phương.

Hôm nay, thầy giáo cho Minh bài toán sau:

Cho số tự nhiên ~n~, sau đó phân tích ~n = k_1 + k_2 + k_3 + k_4 + \ldots~ Trong đó, các giá trị ~k_1, k_2, k_3, k_4, \ldots~ được tìm theo quy tắc:

• Tìm số chính phương ~k_1~ lớn nhất không vượt quá ~n~.
• Tiếp theo, thực hiện tương tự bước trên với ~n = n - k_1~ để tìm ~k_2~.
• Để tìm ~k_3, k_4, \ldots~ thực hiện tương tự như trên cho đến khi ~n = 0~.

Yêu cầu

Hãy tính giá trị của ~S = (k_1)^1 + (k_2)^2 + (k_3)^3 + (k_4)^4 + \ldots~

Theo em, giá trị của ~S~ là bao nhiêu?

Dữ liệu vào

Gồm một số nguyên dương ~n~ ~(1 \le n \le 10^{14})~.

Kết quả

Gồm một số nguyên duy nhất là giá trị ~S~ tìm được.

Ràng buộc dữ liệu

• Có 60% test có ~1 \le n \le 10^6~.
• Có 40% test có ~10^6 < n \le 10^{14}~.

Ví dụ

Ví dụ 1

INPUT

30

OUTPUT

42

Giải thích: Với ~n = 30~, ta có ~n = 25 + 4 + 1~ nên ~S = 25^1 + 4^2 + 1^3 = 42~.

Ví dụ 2

INPUT

25

OUTPUT

25

Giải thích: Với ~n = 25~, nên ~S = 25^1 = 25~.

Trong buổi biểu diễn văn nghệ cuối năm của một trường trung học cơ sở, có ~n~ học sinh tham gia và được đánh số từ ~1~ đến ~n~. Các học sinh có chiều cao lần lượt là ~h_1, h_2, \ldots, h_n~. Ban tổ chức muốn xếp các bạn có cùng chiều cao chung nhóm. Các nhóm này sẽ biểu diễn tiết mục múa để có đội hình đẹp. Còn lại, bạn nào có chiều cao riêng biệt (không bằng chiều cao với học sinh nào khác) sẽ được xếp vào cùng một nhóm riêng để diễn kịch.

Yêu cầu

Em hãy giúp ban tổ chức xác định chiều cao và số học sinh của từng nhóm múa. Riêng nhóm kịch chỉ cần xác định có bao nhiêu học sinh.

Dữ liệu vào

Gồm hai dòng:

• Dòng thứ nhất chứa một số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~h_1, h_2, \ldots, h_n~, giữa hai số cách nhau một khoảng trắng ~(1 \le h_i \le 10^9;\ 1 \le i \le n)~.

Kết quả

Gồm nhiều dòng:

• Các dòng đầu, mỗi dòng ghi hai số nguyên lần lượt là chiều cao và số lượng học sinh của từng nhóm múa, theo thứ tự tăng dần theo chiều cao, giữa hai số cách nhau một khoảng trắng. Lưu ý, nếu không có nhóm múa nào thì không có các dòng này.
• Dòng cuối ghi một số nguyên là số học sinh của nhóm kịch.

Ràng buộc dữ liệu

• Có 60% test có ~1 \le n \le 10^3~.
• Có 40% test có ~10^3 < n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

7
165 164 150 150 164 165 165

OUTPUT

150 2
164 2
165 3
0

Ví dụ 2

INPUT

6
170 180 154 165 180 170

OUTPUT

170 2
180 2
2

Ông Nam có một tin nhắn quan trọng cần chuyển đến các nhân viên của mình. Nội dung tin nhắn là một xâu kí tự gồm chữ cái in thường và in hoa trong bảng chữ cái tiếng Anh. Để bảo mật thông tin, ông Nam đã mã hóa nội dung tin nhắn của mình theo cách sau:

• Ký tự thứ nhất (ký tự đầu tiên) sẽ được đổi thành mã ASCII của nó.
• Ký tự thứ hai: Nếu nó là kí tự in hoa thì dịch chuyển qua phải ~k~ đơn vị theo vòng của bảng chữ cái A...Z. Còn nếu nó là kí tự in thường thì dịch chuyển qua phải ~k - 1~ đơn vị theo vòng của bảng chữ cái a...z.
• Với các ký tự tiếp theo, thực hiện trình tự mã hóa như hai ký tự trên.

Sau khi mã hóa, ông Nam sẽ có được một xâu ~S~ và gửi cho nhân viên.

Ví dụ: Cần nhắn tin HopGap sau khi mã hóa với ~k = 2~ thì xâu ~S~ sẽ là ~S =~ 72p112I97q.

Yêu cầu

Nhận được tin nhắn, các nhân viên đang loay hoay chưa biết giải mã thế nào. Em hãy giúp các nhân viên trong công ty của ông Nam giải mã tin nhắn nhé!

Dữ liệu vào

Gồm hai dòng:

• Dòng thứ nhất: Chứa một xâu ký tự ~S~ khác rỗng có độ dài không quá ~10^5~ ký tự, các kí tự là số và chữ trong bảng chữ cái tiếng Anh.
• Dòng thứ hai: Chứa số nguyên ~k~ ~(1 \le k \le 10^9)~.

Lưu ý, dữ liệu vào nếu các kí tự là số luôn đảm bảo là mã ASCII của các kí tự trong bảng chữ cái tiếng Anh.

Kết quả

Gồm một dòng chứa nội dung tin nhắn sau khi giải mã.

Ràng buộc dữ liệu

• Có 50% số test đầu tiên với xâu ~S~ có độ dài không quá ~10^3~ ký tự.
• Có 50% số test cuối cùng có giới hạn như trong đề.

Ví dụ

Ví dụ 1

INPUT

72p112I97q
2

OUTPUT

HopGap

Ví dụ 2

INPUT

84j101C111q78g119
3

OUTPUT

TheZooNew

Hè rồi, Minh có chuyến du lịch leo núi thú vị. Trong chuyến du lịch này, Minh đã đi qua ~n~ địa điểm được đánh số theo thứ tự từ ~1~ đến ~n~. Các điểm này có độ cao là một dãy số nguyên dương ~h~ với các phần tử là ~h_1, h_2, \ldots, h_n~. Trong đó, đoạn hành trình gồm có leo núi trước rồi xuống núi thì được gọi là hành trình chinh phục ngọn núi. Tức là, hành trình này đi qua một đoạn con liên tiếp của dãy ~h~ có độ cao tăng dần rồi giảm dần và số địa điểm đi qua trong hành trình này gọi là độ dài của một hành trình chinh phục ngọn núi.

Yêu cầu

Em hãy cho biết độ dài lớn nhất một hành trình chinh phục ngọn núi trong chuyến du lịch này của Minh là bao nhiêu?

Dữ liệu vào

Gồm hai dòng:

• Dòng thứ nhất: Chứa số nguyên ~n~ ~(3 \le n \le 10^6)~.
• Dòng thứ hai: Chứa ~n~ số nguyên ~h_1, h_2, \ldots, h_n~ ~(0 < h_i \le 10^9)~, giữa hai số cách nhau một khoảng trắng.

Kết quả

Ghi ra một số nguyên là đáp án cần tìm. Nếu Minh không có một hành trình chinh phục ngọn núi nào thì ghi ~0~.

Ràng buộc dữ liệu

• Có 60% test có ~1 \le n \le 10^3~.
• Có 40% test có ~10^3 < n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

12
1 1 2 3 4 6 4 2 1 2 3 1

OUTPUT

8

Ví dụ 2

INPUT

5
9 8 1 10 12

OUTPUT

0