Học sinh giỏi lớp 9 tỉnh Bắc Ninh 2025-2026

Cho ba số nguyên dương \(a, b, c\). Gọi \(T_a\) là tổng các ước số dương của số \(a\); \(T_b\) là tổng các ước số dương của số \(b\); \(T_c\) là tổng các ước số dương của số \(c\).

Yêu cầu: Tìm giá trị lớn nhất trong ba số \(T_a, T_b, T_c\).

Input

• Một dòng duy nhất chứa ba số nguyên dương \(a, b, c\) (\(a, b, c \le 10^{12}\)) cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là giá trị lớn nhất tìm được.

Example

8 13 10

18

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(a, b, c \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(a, b, c \le 10^{12}\).

Số nguyên tố là số nguyên dương lớn hơn \(1\) và có đúng hai ước số dương là \(1\) và chính nó. Một số nguyên \(x\) được gọi là số nguyên tố đặc biệt nếu \(x\) là số nguyên tố và số viết ngược lại của \(x\) cũng là số nguyên tố.

Ví dụ: Số \(13\) là số nguyên tố đặc biệt vì \(13\) và \(31\) đều là số nguyên tố, số \(23\) không phải là số nguyên tố đặc biệt vì \(23\) là số nguyên tố nhưng \(32\) không phải là số nguyên tố.

Cho dãy số \(A\) có \(N\) phần tử nguyên \(A_1, A_2, \dots, A_N\) và một số nguyên dương \(Q\).

Yêu cầu: Với mỗi cặp chỉ số \(L, R\) (\(1 \le L \le R \le N\)) trong \(Q\) truy vấn, đếm số lượng số nguyên tố đặc biệt trong đoạn con \(A_L, A_{L+1}, \dots, A_R\).

Input

• Dòng 1: Ghi hai số nguyên dương \(N, Q\) (\(1 \le N \le 10^6; 1 \le Q \le 10^6\)).
• Dòng 2: Ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^7 \le A_i \le 10^7; i = 1, 2, \dots, N\)).
• \(Q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(L, R\) (\(1 \le L \le R \le N\)).

Output

• Ghi ra \(Q\) dòng, mỗi dòng ghi một số nguyên là kết quả tương ứng với mỗi truy vấn.

Example

5 3
13 23 31 7 11
1 3
2 4
1 5

2
2
4

Constraints

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \le 10^3; |A_i| \le 10^6\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Cho xâu ký tự \(S\) chỉ gồm các kí tự in hoa, in thường, chữ số. Xâu con là xâu được lấy ra từ xâu \(S\) một số ký tự liên tiếp. Xâu \(S\) cũng được coi là xâu con của chính nó. Một xâu là đối xứng nếu đọc từ phải sang trái cũng thu được kết quả giống như đọc từ trái sang phải.

Ví dụ: Các xâu madam, IOI, aba6aba là các xâu đối xứng, các xâu Caab, 92328, abda là các xâu không đối xứng.

Yêu cầu: Cho xâu \(S\) có độ dài không quá \(10^4\) kí tự chỉ gồm các kí tự in hoa, in thường, chữ số, tìm độ dài xâu con đối xứng dài nhất trong xâu \(S\).

Input

• Đọc từ tệp văn bản DOIXUNG.INP chứa xâu ký tự \(S\).

Output

• Ghi ra tệp văn bản DOIXUNG.OUT một số nguyên duy nhất là kết quả cần tìm.

Example

Caaba1ababa

7

Scoring

• Subtask \(1\) (\(70\%\) số điểm): Xâu \(S\) có độ dài không quá \(500\) kí tự.
• Subtask \(2\) (\(30\%\) số điểm): Không có ràng buộc gì thêm (độ dài xâu \(S \le 10^4\)).

Cuộc thi Robocon 2030 dự kiến tổ chức cuộc thi nhảy xa trên cọc cho các chiến binh rô bốt. Ban tổ chức cuộc thi quy định luật chơi được mô tả như sau:

Trên sa bàn có \(N\) cọc được sắp xếp trên một đường thẳng, các cọc được đánh số từ trái sang phải theo thứ tự từ \(1\) đến \(N\). Khoảng cách giữa các cọc là bằng nhau. Cọc thứ \(i\) có chiều cao là \(A_i\). Ban tổ chức cho trước một số nguyên \(P\) không âm làm điều kiện ràng buộc giữa chiều cao của cọc đích và chiều cao của cọc xuất phát trong luật chơi. Mỗi rô bốt khi tham gia cuộc thi được thực hiện một bước nhảy.

Bước nhảy của rô bốt là \(1\) lần nhảy từ cọc xuất phát \(i\) bất kì đến cọc đích \(j\) thỏa mãn các điều kiện:

• \(1 \le i \le j \le N\);
• \(A_j - A_i \ge P\);

Khi đó \(j - i\) gọi là độ dài của bước nhảy. Bước nhảy xa nhất là bước nhảy có độ dài lớn nhất. Các rô bốt có bước nhảy xa nhất được tham gia vòng chung kết của cuộc thi.

Ví dụ: Sa bàn với \(6\) cọc có chiều cao các cọc tương ứng \(A = (4, 3, 7, 2, 6, 4)\), với \(P = 3\) ta có các bước nhảy thỏa mãn là:

• Rô bốt nhảy từ cọc \(1\) sang cọc \(3\) có độ dài bước nhảy bằng \(2\);
• Rô bốt nhảy từ cọc \(2\) sang cọc \(3\) có độ dài bước nhảy bằng \(1\);
• Rô bốt nhảy từ cọc \(2\) sang cọc \(5\) có độ dài bước nhảy bằng \(3\);
  \(\rightarrow\) Bước nhảy xa nhất có độ dài là \(3\).

Yêu cầu: Tìm độ dài bước nhảy xa nhất mà rô bốt có thể đạt được trong cuộc thi trên.

Input

• Dòng 1: Ghi 2 số nguyên \(N\) và \(P\) (\(1 \le N \le 10^6; 0 \le P \le 10^9\)).
• Dòng 2: Ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \le A_i \le 10^9; i = 1, 2, \dots, N\)).

Output

• Ghi ra một số nguyên duy nhất là độ dài bước nhảy xa nhất tìm được. Nếu không có bước nhảy nào thỏa mãn thì ghi kết quả bằng \(0\).

Example

6 3
4 3 7 2 6 4

3

7 2
15 2 7 10 1 8 3

4

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \le 2000\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 10^6\).