THT Bảng B - Vòng Khu vực MB & MT 2026

Alice viết lần lượt từng số của dãy số nguyên \((a_1, a_2, \dots, a_N)\) lên vòng tròn theo chiều kim đồng hồ.

Với số nguyên dương \(K\), Alice muốn chọn một đoạn gồm không quá \(K\) phần tử liên tiếp trên vòng tròn để tổng là lớn nhất.

Ví dụ, với dãy số \((5, -1, 4, 1, -1, 5, -6, 6)\):

• Nếu \(K = 4\), Alice có thể chọn \(6 + 5 + (-1) + 4 = 14\) là lớn nhất.
• Nếu \(K = 3\), Alice có thể chọn \(6 + 5 = 11\) là lớn nhất.

Yêu cầu: Cho dãy số \((a_1, a_2, \dots, a_N)\) và số nguyên dương \(K\), hãy giúp Alice tính tổng lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(N, K\) (\(K \le N \le 3 \cdot 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(|a_i| \le 10^9\)).

Output

• Gồm một dòng chứa một số là tổng lớn nhất có thể đạt được.

Example

8 4
5 -1 4 1 -1 5 -6 6

14

8 3
5 -1 4 1 -1 5 -6 6

11

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 300\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 3000\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc nào thêm.

Ta nhận thấy rằng với \(n\) lớn, các chữ số cuối cùng của \(n!\) luôn có dạng \(\dots \overline{d_k d_{k-1} \dots d_2 d_1 00 \dots 00}\), với \(d_1 \neq 0\). Hãy tìm các chữ số \(d_k, d_{k-1}, \dots, d_2, d_1\) ở trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(T\) (số lượng test cases) và \(k\) (số lượng chữ số cần tìm).
• Dòng thứ hai chứa \(T\) số nguyên dương \(n_1, n_2, \dots, n_T\) là các test case.

Output

• Một dòng duy nhất chứa \(T\) xâu, xâu thứ \(i\) gồm \(k\) chữ số \(\overline{d_k d_{k-1} \dots d_2 d_1}\) viết liền kề, mỗi xâu cách nhau bằng một khoảng trắng.

Constraints

• \(T = 5\)
• Subtask \(1\) (\(10\%\)): \(n \leq 10^6, k = 1\)
• Subtask \(2\) (\(20\%\)): \(n \leq 10^6, k = 6\)
• Subtask \(3\) (\(35\%\)): \(n \leq 10^{18}, k = 1\)
• Subtask \(4\) (\(25\%\)): \(n \leq 10^{18}, k = 6\)
• Subtask \(5\) (\(10\%\)): \(n \leq 10^{18}, k = 9\)

Example

4 2
10 11 12 13

88 68 16 08

Một số nguyên dương \(X\) được gọi là số đặc biệt nếu \(X\) chia hết cho tổng các chữ số của nó.
Ví dụ số \(1, 9, 10, 12, 18\) là các số đặc biệt, còn số \(13, 15\) không phải là số đặc biệt.

Định nghĩa \(f^1(X)\) là số đặc biệt nhỏ nhất lớn hơn \(X\), \(f^2(X)\) là số đặc biệt nhỏ nhất lớn hơn \(f^1(X), \dots, f^K(X)\) là số đặc biệt nhỏ nhất lớn hơn \(f^{K-1}(X)\).

Một cách hình thức: \(f^K(X) = f^1(f^{K-1}(X))\) với \(K > 1\).

Yêu cầu: Cho hai số nguyên dương \(X, K\), hãy tìm \(f^K(X)\).

Input

• Dòng đầu chứa số nguyên dương \(T\) là số bộ dữ liệu (\(T \le 10^3\)).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(X, K\) (\(X, K \le 10^{12}\)).

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Example

3
9 2
1 11
2025 2026

12
18
15519

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(X \le 10^9\); \(K \le 10^3\); \(T = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(X \le 10^9\); \(K \le 10^7\); \(T = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(X \le 10^9\); \(K \le 10^9\); \(T = 1\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc nào thêm.