Vòng chung kết Hue ICT2025 - Bảng Junior

Trên bảng \(A\) gồm \(n\) hàng và \(n\) cột, các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Tiến hành điền các số theo quy tắc: Trên hàng \(i\) (\(1 \le i \le n\)) lần lượt điền các số chẵn bắt đầu từ \(2 \cdot i\). Cụ thể, các số \(2 \cdot i, 2 \cdot (i + 1), \dots, 2 \cdot (i + n - 1)\) được điền trên hàng \(i\).

Ví dụ, với \(n = 4\) ta có bảng số sau:

Yêu cầu: Cho \(n\), hãy tính tổng các số điền trong bảng.

Input

• Gồm một số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• Gồm một số là tổng tính được chia dư cho \(10^9 + 7\).

Example

2

16

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n \le 10^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^6\).
• Subtask \(3\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.

Số nguyên \(p\) được gọi là hoàn hảo nếu \(p > 0\) và tổng tất cả các ước của \(p\) bằng \(2 \cdot p\). Ví dụ, số \(6\) là số hoàn hảo vì tổng các ước của \(6\) là \(1 + 2 + 3 + 6 = 12 = 2 \cdot 6\).

Yêu cầu: Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và số \(w\), hãy đếm số cách chọn một đoạn số mà tổng các phần tử thuộc đoạn là số hoàn hảo không vượt quá \(w\), cụ thể cần đếm số cách chọn hai chỉ số \(L, R\) thỏa mãn: \(1 \le L \le R \le n\) và \(a_L + a_{L+1} + \dots + a_R\) là số hoàn hảo không vượt quá \(w\).

Input

• Dòng đầu gồm hai số nguyên dương \(n, w\) (\(n \le 10^5; w \le 10^{15}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9; 1 \le i \le n\)).

Output

• Gồm một dòng chứa một số là số cách chọn thỏa mãn.

Example

3 6
6 6 -6

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 1000; w \le 6\).
• Subtask \(2\) (\(30\%\) số điểm): \(w \le 6\).
• Subtask \(3\) (\(30\%\) số điểm): \(w \le 10^6\).
• Subtask \(4\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.

Trong một trò chơi trên bảng vuông \((n + 1) \times (n + 1)\), các dòng từ trên xuống dưới được đánh số từ \(0\) đến \(n\), các cột từ trái sang phải được đánh số từ \(0\) đến \(n\), ô ở dòng thứ \(i\) và cột thứ \(j\) gọi là ô \((i, j)\). Bảng có đúng \(n\) ô chứa quà, quà thứ \(i\) (\(1 \le i \le n\)) nằm ở ô \((i, p[i])\) và có giá trị là \(c[i]\).

Ban đầu bạn ở ô \((0, 0)\), mỗi bước có thể đi sang phải hoặc đi xuống dưới một ô.

Giá trị của một đường đi là tổng giá trị của các ô chứa quà mà đường đi đó đi qua. Bạn cần tìm ra đường đi có giá trị lớn nhất.

Để tăng thêm thử thách, trò chơi có thêm \(m\) màn, mỗi màn chơi có các ô bị cấm không được đi vào là các ô nằm trong hình chữ nhật có ô trái trên là \((u, y)\) và ô phải dưới là \((x, v)\). Chú ý: Mỗi màn chơi độc lập với nhau, tức là việc cấm hình chữ nhật chỉ là giả định ở mỗi màn chơi.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, m\) (\(0 \le n, m \le 3 \cdot 10^5\)).
• \(n\) dòng sau, mỗi dòng gồm hai số nguyên \(p[i]\) và \(c[i]\) (\(1 \le i \le n; 1 \le p[i] \le n; 1 \le c[i] \le 10^9\)). Dữ liệu đảm bảo rằng dãy \(p\) phân biệt.
• \(m\) dòng tiếp theo, mỗi dòng gồm bốn số nguyên \(x, y, u, v\) (\(1 \le u \le x \le n; 1 \le y \le v \le n\)) mô tả hình chữ nhật bị cấm ở màn chơi tương ứng.

Output

• Dòng đầu tiên in ra giá trị của đường đi lớn nhất khi không có hình chữ nhật bị cấm.
• \(m\) dòng tiếp theo in ra kết quả của màn chơi thêm tương ứng.

Example

3 3
2 5
3 4
1 7
1 1 1 3
1 1 3 3
1 1 1 1

9
7
0
9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(m = 0\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc nào thêm.

Cho bảng số \(A\) gồm \(m\) hàng và \(n\) cột, các hàng được đánh số từ \(1\) đến \(m\) từ trên xuống, các cột được đánh số từ \(1\) đến \(n\) từ trái sang. Ô nằm giao giữa hàng \(i\) và cột \(j\) gọi là ô \((i, j)\) và chứa số nguyên không âm \(a(i, j)\) có giá trị không vượt quá \(10^5\).

Thao tác \(sort(j)\) sẽ sắp xếp các hàng trong bảng theo giá trị không giảm của các số ở cột \(j\) (\(j = 1, 2, \dots, n\)), nếu số ở hai hàng tại cột \(j\) có giá trị bằng nhau thì hàng nào đang xếp trước sẽ được ưu tiên xếp trước. Cụ thể, với hai hàng \(i_1, i_2\) (hàng \(i_1\) đang xếp trước hàng \(i_2\)), sau khi thực hiện thao tác \(sort(j)\) thì hàng \(i_2\) sẽ chỉ được xếp trước hàng \(i_1\) nếu \(a(i_2, j) < a(i_1, j)\).

Xét dãy gồm \(s\) thao tác sắp xếp \(sort(j_1), sort(j_2), \dots, sort(j_s)\) và \(q\) truy vấn, truy vấn thứ \(t\) (\(1 \le t \le q\)) mô tả bằng ba số nguyên \(d_t, u_t, v_t\) (\(1 \le d_t \le s; 1 \le u_t \le m; 1 \le v_t \le n\)) có nghĩa là khi thực hiện lần lượt dãy thao tác sắp xếp ngoại trừ thao tác thứ \(d_t\) thì ô \((u_t, v_t)\) của bảng có giá trị là bao nhiêu.

Yêu cầu: Cho bảng số \(A\), dãy \(s\) và \(q\) truy vấn, với truy vấn thứ \(t\) hãy xác định ô \((u_t, v_t)\) trong bảng sau khi thực hiện \(s - 1\) thao tác sắp xếp (bỏ thao tác thứ \(d_t\)).

Input

• Dòng đầu gồm bốn số nguyên dương \(m, n, s, q\) (\(m \cdot n \le 10^5; s \le 10^5; q \le 10^5\)).
• Dòng thứ \(i\) (\(1 \le i \le m\)) trong số \(m\) dòng tiếp theo chứa \(n\) số nguyên không âm mô tả dòng thứ \(i\) của bảng \(A\).
• Dòng tiếp theo chứa \(s\) số nguyên (mỗi số có giá trị thuộc \([1, n]\)), mô tả dãy gồm \(s\) thao tác.
• Dòng thứ \(t\) (\(1 \le t \le q\)) trong \(q\) dòng tiếp theo chứa ba số nguyên \(d_t, u_t, v_t\) mô tả truy vấn thứ \(t\).

Output

• Gồm \(q\) dòng, dòng thứ \(t\) (\(1 \le t \le q\)) chứa một số nguyên là câu trả lời cho truy vấn thứ \(t\).

Example

3 3 4 3
1 1 3
1 1 2
1 1 1
1 2 3 1
4 1 1
4 1 3
1 3 3

1
1
3

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 100; s \le 100\) và tất cả các truy vấn giá trị \(d_t\) đều bằng \(1\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 100\) và tất cả các truy vấn giá trị \(d_t\) đều bằng \(1\).
• Subtask \(3\) (\(20\%\) số điểm): \(m \le 100\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(5\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.