Trong lễ khai mạc Hội xuân tại quảng trường Võ Nguyên Giáp (tỉnh Thái Nguyên), Ban tổ chức có một phần quà đặc biệt dành cho các bạn học sinh yêu thích toán học và lập trình.

Thử thách đưa ra như sau:

Cho một số nguyên dương n. Bạn cần tính tổng lập phương của tất cả các số tự nhiên từ 1 đến n. Ký hiệu tổng này là S(n):

S(n) = 1^3+ 2^3 + 3^3+...+ n^3

Vì kết quả S(n) có thể rất lớn, Ban tổ chức chỉ yêu cầu bạn in ra phần dư của S(n) khi chia cho 2026^2

Yêu cầu: Hãy lập trình giúp các bạn học sinh giải quyết thử thách trên để nhận phần quà từ Ban tổ chức.

Dữ liệu vào: Đọc từ bàn phím (thiết bị vào chuẩn):

• Một số nguyên dương n (1 ≤ n ≤ 10^12).

Kết quả: Ghi ra màn hình (thiết bị ra chuẩn):

• Số nguyên duy nhất là giá trị S(n) mod 2026^2 (mod là phép chia lấy phần dư)

Ví dụ:

Input 01:

3

Output 01:

36

Giải thích: 1^3 + 2^3 + 3^3 = 36; 36 mod 2026^2 = 36

Input 02:

10

Output 02:

3025

Ràng buộc:

• Có 50% số điểm tương ứng với 1 < N ≤ 10.

• Có 30% số điểm tương ứng với 10 < N ≤ 10^2.

• Có 20% số điểm còn lại tương ứng với 10^2 < N ≤ 10^12.

Trong trò chơi "Đi tìm kho báu" tại Hội xuân, Tí tìm thấy một mẫu giấy ghi một dãy các ký tự bao gồm cả chữ cái và chữ số. Để mở được hòm kho báu, Tí cần trích xuất tất cả các số tự nhiên xuất hiện trong dãy đó và tìm số lớn nhất. Biết rằng các số trong dãy được phân cách nhau bởi các ký tự chữ cái.

Yêu cầu: Hãy giúp Tí tìm số tự nhiên lớn nhất có trong xâu ký tự cho trước.

Dữ liệu vào: Đọc từ bàn phím (thiết bị vào chuẩn):

• Một xâu ký tự S có độ dài không quá 10^5 chỉ chứa các chữ cái tiếng Anh (hoa, thường) và các chữ số từ 0 đến 9.

Kết quả: Ghi ra màn hình (thiết bị ra chuẩn):

• Số tự nhiên lớn nhất tìm được. Nếu trong xâu không có số nào, ghi -1.

Ví dụ:

Input 01:

ThaiNguyenNo1

Output 01:

1

Input 02:

Hoi28Xuan12ThaiNguyen2026

Output 02:

2026

Input 03:

XuanBinhNgo

Output 03:

-1

Ràng buộc:

• Có 20% số điểm tương ứng với xâu S chỉ xuất hiện một số tự nhiên.

• Có 30% số điểm tương ứng với xâu S có độ dài < 100, các số xuất hiện đều nhỏ hơn 10^6

• Có 30% số điểm tương ứng với xâu S có độ dài ≤ 10^4, các số xuất hiện đều nhỏ hơn 10^9.

• Có 20% sô điểm còn lại tương ứng với xâu S có độ dài ≤ 10^5 , các số xuất hiện có tồi đa 4000 chữ số.

Một Trung tâm Ngoại ngữ có tổ chức lớp học trực tuyến (online), trong đó có n tiết học (từ 1 đến n), tiết học thứ i có thời lượng ai (tính bằng giây). Học viên có thể đăng ký học liên tiếp nhiều tiết học. Hãy tìm số lượng tiết học liên tiếp tối đa mà một học viên có thể tham gia trong một khoảng thời gian không vượt quá thời gian rảnh của họ.

Yêu cầu: Có q truy vấn, mỗi truy vấn cho biết thời gian rảnh của học viên là t giây. Với mỗi truy vấn, bạn cần tìm số lượng tiết học liên tiếp nhiều nhất mà học viên có thể tham gia trong thời gian không quá t giây.

Dữ liệu: Đọc từ bàn phím (thiết bị vào chuẩn):

• Dòng đâu tiên chứa số nguyên n (1 ≤ n ≤ 10^4) là số lượng tiết học.

• Dòng thứ hai chứa n số nguyên (cách nhau 1 dấu cách) a1, a2,..., an (1 ≤ ai ≤ 10^4) là thời lượng của từng tiết.

• Dòng thứ ba chứa số nguyên q (1 ≤ q ≤ 10^4) là số lượng truy vấn.

• q dòng tiếp theo, mỗi dòng chứa một số nguyên t (1 ≤ t ≤ 10^8) là thời gian rảnh của học viên.

Kết quả: Ghi ra màn hình (thiết bị ra chuẩn):

Với mỗi truy vấn, in ra số lượng tiết học liên tiếp nhiều nhất mà học viên có thể tham gia trong thời gian t giây. Lưu ý học viên không bắt buộc phải tham gia từ tiết 1.

Ví dụ:

Input:

5
4 2 3 1 5
3
7
10
15

Output:

3
4
5

• Truy vấn 1: t = 7. Có thể tham gia 3 tiết học liên tiếp 2, 3, 4 có tổng thời gian học là: 2 + 3 + 1 = 6 ≤ 7.

• Truy vấn 2: t = 10. Có thể tham gia 4 tiết học liên tiếp 1, 2, 3, 4 có tổng thời gian học là: 4 + 2 + 3 + 1 = 10 ≤ 10.

• Truy vấn 3: t = 15. Có thể tham gia tất cả 5 tiết học có tổng thời gian học là 4 + 2 + 3 + 1 + 5 = 15 ≤ 15.

Ràng buộc:

• Có 40% số điểm tương ứng với 10 < n,q ≤ 5.10^2.

• Có 30% số điểm tương ứng với 5.10^2 < n,q ≤ 10^3

• Có 30% số điểm tương ứng với 10^3 < n,q ≤ 10^4.