THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Tâm hình vuông (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)	100 (p)	0.25s	512M
2	Lựa chọn giá trị tối ưu (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)	100 (p)	1.0s	512M
3	Đếm số (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)	100 (p)	1.0s	512M

1. Tâm hình vuông (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)

Điểm: 100 (p) Thời gian: 0.25s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Xét một bảng vuông kích thước \(N \times N\).
Các ô trong bảng được điền các số từ \(1\) đến \(N^2\) theo thứ tự: từ trái sang phải, từ trên xuống dưới.

Hãy tính tổng các phần tử ở trung tâm của bảng:

Nếu \(N\) là số lẻ: trung tâm là một ô duy nhất (\(1 \times 1\)).
Nếu \(N\) là số chẵn: trung tâm là \(4\) ô tạo thành hình vuông (\(2 \times 2\)).

Input

Một dòng chứa số nguyên \(N\) (\(1 \le N \le 10^{18}\)).

Output

In ra một số nguyên là tổng các phần tử ở vùng trung tâm.

Example

Test 1

Input

Output

Test 2

Input

Output

Scoring

Subtask \(1\) (\(80\%\) số điểm): \(N \le 10^3\).
Subtask \(2\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

2. Lựa chọn giá trị tối ưu (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai mảng số nguyên \(A\) và \(B\), mỗi mảng gồm \(N\) phần tử, với điều kiện \(B_i \ge A_i\) với mọi \(1 \le i \le N\).

Tại mỗi vị trí \(i\), bạn phải chọn chính xác một trong hai giá trị:

Chọn \(A_i\) và không mất chi phí;
Hoặc chọn \(B_i\) và phải trả chi phí \(C\).

Giả sử với một giá trị \(C\) đã cho, ta đưa ra lựa chọn tại mỗi vị trí. Khi đó, giá trị của phương án được tính bằng:

Tổng các giá trị đã chọn,
Trừ đi tổng chi phí phải trả cho các vị trí chọn \(B_i\).

Nếu có \(k\) vị trí chọn \(B_i\), thì tổng chi phí là \(k \cdot C\).

Yêu cầu

Cho \(Q\) giá trị khác nhau của \(C\). Với mỗi giá trị \(C\), hãy tính giá trị lớn nhất có thể đạt được.

Input

Dòng đầu chứa hai số nguyên \(N, Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).
Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(0 \le A_i \le 10^9\)).
Dòng thứ ba chứa \(N\) số nguyên \(B_1, B_2, \ldots, B_N\) (\(0 \le B_i \le 10^9\)).
Dòng thứ tư chứa \(Q\) số nguyên \(C_1, C_2, \ldots, C_Q\) (\(0 \le C_i \le 10^9\)).

Output

In ra \(Q\) dòng, mỗi dòng là giá trị lớn nhất tương ứng với một \(C\).

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(N, Q \le 2000\).
Subtask \(2\) (\(30\%\) số điểm): \(A_i, B_i, C_i \le 2000\).
Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung.

Example

Test 1

Input

Output

18
13
11

Note

Ta xét lần lượt từng giá trị \(C\):

Với \(C = 1\):
- Vị trí 1: chọn \(B_1 = 8\) tốt hơn chọn \(A_1 = 5\), vì tăng thêm \(3\) và chỉ mất phí \(1\).
- Vị trí 2: chọn \(B_2 = 3\) tốt hơn chọn \(A_2 = 2\), vì tăng thêm \(1\) và mất phí \(1\).
- Vị trí 3: chọn \(B_3 = 10\) tốt hơn chọn \(A_3 = 4\), vì tăng thêm \(6\) và mất phí \(1\).
- Khi đó ta chọn cả ba giá trị trong mảng \(B\). Tổng nhận được là \(8 + 3 + 10 = 21\), tổng chi phí là \(3 \cdot 1 = 3\). Giá trị cuối cùng là \(21 - 3 = 18\).
Với \(C = 4\):
- Vị trí 1: chọn \(A_1 = 5\), vì nếu chọn \(B_1 = 8\) thì chỉ hơn \(3\) nhưng phải trả phí \(4\).
- Vị trí 2: chọn \(A_2 = 2\), vì \(B_2 = 3\) chỉ hơn \(1\).
- Vị trí 3: chọn \(B_3 = 10\), vì hơn \(6\) so với \(A_3 = 4\), lớn hơn chi phí \(4\).
- Tổng nhận được là \(5 + 2 + 10 = 17\), tổng chi phí là \(4\). Giá trị cuối cùng là \(17 - 4 = 13\).
Với \(C = 7\):
- Ở cả ba vị trí, phần tăng thêm khi chọn \(B_i\) đều không vượt quá chi phí \(7\).
- Vì vậy, tốt nhất là chọn toàn bộ \(A\). Tổng giá trị là \(5 + 2 + 4 = 11\).

3. Đếm số (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai số nguyên dương \(A\) và \(B\) (\(A \le B\)).

Một số nguyên \(X\) được gọi là thỏa mãn nếu đồng thời thỏa cả ba điều kiện sau:

\(A \le X \le B\);
Tổng các chữ số của \(X\) là một số nguyên tố;
Số lượng ước số dương của \(X\) là một số chẵn.

Yêu cầu

Cho \(T\) truy vấn. Mỗi truy vấn gồm hai số \(A_i, B_i\). Với mỗi truy vấn, hãy đếm số lượng số \(X\) thỏa mãn trong đoạn \([A_i, B_i]\).

Input

Dòng đầu tiên chứa số nguyên dương \(T\).
\(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(A_i, B_i\) (\(A_i \le B_i\)).

Output

Gồm \(T\) dòng, mỗi dòng in ra một số nguyên là kết quả của truy vấn tương ứng.

Example

Test 1

Input

2
1 9
10 15

Output

4
3

Note

Với đoạn \([1, 9]\): Các số thỏa mãn là: \(2, 3, 5, 7\) (tổng chữ số là số nguyên tố, và số ước của mỗi số là chẵn).
Với đoạn \([10, 15]\):
- \(10\): tổng chữ số \(= 1\) (không phải số nguyên tố) \(\rightarrow\) loại.
- \(11\): tổng \(= 2\) (nguyên tố), số ước \(= 2\) (chẵn) \(\rightarrow\) thỏa mãn.
- \(12\): tổng \(= 3\) (nguyên tố), số ước \(= 6\) (chẵn) \(\rightarrow\) thỏa mãn.
- \(13\): tổng \(= 4\) (không nguyên tố) \(\rightarrow\) loại.
- \(14\): tổng \(= 5\) (nguyên tố), số ước \(= 4\) (chẵn) \(\rightarrow\) thỏa mãn.
- \(15\): tổng \(= 6\) (không nguyên tố) \(\rightarrow\) loại.

Các số thỏa mãn là: \(11, 12, 14 \rightarrow\) có \(3\) số.

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(T = 1; 1 \le A_i \le B_i \le 10^3\).
Subtask \(2\) (\(40\%\) số điểm): \(T \le 10^5; 1 \le A_i \le B_i \le 10^7\).
Subtask \(3\) (\(20\%\) số điểm): \(T \le 10^5; 1 \le A_i \le B_i \le 10^{14}\).