Bài tập

Cho một lưới ô vuông gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) tới \(r\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) tới \(c\) theo thứ tự từ trái qua phải. Ô ở hàng \(x\) và cột \(y\) được kí hiệu là ô \((x, y)\).

Xuất phát từ góc trái trên \((1, 1)\), bạn cần đi xuống góc phải dưới \((r, c)\). Ở mỗi bước, bạn được di chuyển từ vị trí hiện tại (giả sử là ô \((x, y)\)) một bước theo một trong ba hướng: sang phải (sang ô \((x, y + 1)\)), xuống dưới (sang ô \((x + 1, y)\)) hoặc chéo xuống (sang ô \((x + 1, y + 1)\)), như hình minh họa dưới đây:

\begincenter

\endcenter

Bạn được cho \(q\) câu hỏi, mỗi câu hỏi gồm hai số \(r\) và \(c\). Hãy đếm số cách đi từ ô \((1, 1)\) tới ô \((r, c)\) ở từng câu hỏi. Do kết quả có thể rất lớn, bạn chỉ cần in ra đáp số theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(q\) \((1 \leq q \leq 10^5)\) cho biết số câu hỏi.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq 2300)\) thể hiện một câu hỏi.

Output

Với mỗi câu hỏi, in ra một số nguyên là số cách đi từ ô \((1, 1)\) đến ô \((r, c)\) modulo \(998244353\).

Example

2
2 2
3 3

3 13 

Scoring

• Subtask \(1\) (\(33\) điểm): \(q = 1\) và \(r, c \leq 10\)

• Subtask \(2\) (\(17\) điểm): \(q \leq 10^5\) và \(r, c \leq 10\)

• Subtask \(3\) (\(30\) điểm): \(q = 1\) và \(r, c \leq 2300\)

• Subtask \(4\) (\(20\) điểm): \(q \leq 10^5\) và \(r, c \leq 2300\)

Bạn đang thực hiện một chuyến hành trình khám phá các khu vực liên tiếp trên một hòn đảo. Hòn đảo có \(n\) khu vực, được đánh số từ \(1\) đến \(n\). Mỗi khu vực \(i\) chứa lượng tài nguyên là \(A_i\).

Bạn nhận được \(q\) yêu cầu, mỗi yêu cầu cho biết:

• Một khu vực đích \(u\) bạn cần đến.
• Một số nguyên \(v\) --- số lượng chặng dừng tối đa bạn được phép chia.

Bạn cần xác định khu vực khởi hành \(e\) nhỏ nhất sao cho:

• Hành trình từ \(e\) đến \(u\) (liên tiếp, \(e \leq u\)) có thể được chia thành không quá \(v\) chặng.
• Tổng tài nguyên trong mỗi chặng không vượt quá \(M\).
• Dữ liệu đảm bảo luôn có giá trị \(e\) thỏa mãn.

Input

• Dòng đầu tiên gồm ba số nguyên \(n\), \(q\), và \(M\) \((1 \leq n, q \leq 10^5, 1 \leq M \leq 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) \((0 \leq A_i \leq M)\).
• Tiếp theo là \(q\) dòng, mỗi dòng gồm hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i \leq n, 1 \leq v_i \leq 10^9)\).

Output

• Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng --- khu vực bắt đầu \(e\) nhỏ nhất thỏa mãn điều kiện.

Example

5 2 8
1 2 3 4 5
4 2
5 2

1
3

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(1 \leq n, q \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(1 \leq n, q \leq 1000\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

"Tùng tùng tùng...".

Trong buổi học cuối cùng của một năm học đầy kỷ niệm, cô giáo chủ nhiệm muốn tạo ra một món quà nhỏ để ghi nhớ lớp học thân thương. Cô nảy ra một ý tưởng: phát một tờ giấy trắng để tất cả học sinh trong lớp cùng ký tên, tạo thành một kỷ vật đáng nhớ.

Cô xếp \(N\) học sinh ngồi theo hình vòng tròn, được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Sau đó, cô phát một tờ giấy cho một học sinh bất kỳ và yêu cầu bạn ấy ký tên lên đó. Tờ giấy sau đó được truyền đi giữa các học sinh theo quy tắc sau:

• Tờ giấy có thể được chuyền cho học sinh bên trái hoặc bên phải của học sinh đang nắm giữ tờ giấy.
• Ngoài ra, mỗi học sinh còn có thể chọn chuyền tờ giấy cho một học sinh khác là một trong những người bạn thân của họ. Cô giáo được biết trong lớp có \(N-3\) cặp bạn thân và cô đã cố tính sắp xếp, sao cho không có một cặp bạn thân ngồi liền kề, và nếu ta vẽ các đường nối giữa họ trên mặt phẳng, thì không có hai đường nào cắt nhau (ngoại trừ tại các đầu mút). Xem hình minh họa.

Mỗi học sinh chỉ ký tên đúng một lần. Quy trình sẽ kết thúc khi học sinh đầu tiên ký nhận lại tờ giấy, và tạo thành một vòng tuần hoàn khép kín gồm các chữ ký. Lưu ý, ta không tính các tập hợp chữ ký có lực lượng nhỏ hơn 3.

Hai tập hợp chữ ký được xem là khác nhau nếu tồn tại một chữ ký chỉ thuộc một trong hai tập hợp.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) --- số học sinh trong lớp.
• Mỗi dòng trong số \(N - 3\) dòng tiếp theo chứa hai số nguyên \(X_i, Y_i\) \((1 \leq X_i, Y_i \leq N)\) --- là một cặp bạn thân.

Output

In ra một số nguyên --- số tập hợp chữ ký khác nhau mà cô giáo có thể nhận được, lấy phần dư theo \(10^9 + 7\).

Example

5
1 3
3 5

6

6
2 4
4 6
6 2

11

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 13 & \(N \leq 15\)

2 & 18 & \(N \leq 300\)

3 & 34 & \(N \leq 2000\)

4 & 15 & Luôn có cặp bạn thân giữa học sinh \(1\) và \(k\) với mọi \(k = 3, 4, \dots, N - 1\)

5 & 40 & Không có ràng buộc bổ sung

\hline
\endtabular

Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^6, 1 \leq i \leq n \leq 10^6\)).

**Yêu cầu:** Tìm dãy con có tổng các phần tử là lớn nhất trong các dãy con không giảm, nếu có nhiều dãy con thoả mãn thì in ra các dãy con theo thứ tự xuất hiện.

Input

Vào từ file SUBSEQ.INP gồm:

• Dòng đầu: số nguyên dương \(n\);
• Dòng tiếp theo: \(n\) số nguyên dương cách nhau khoảng trắng.

Output

Ghi ra file SUBSEQ.OUT gồm:

• Dòng đầu: tổng lớn nhất tìm được;
• Các dòng tiếp theo: các dãy con thỏa mãn.

Example

10
2 2 3 4 6 6 7 7 8 8

53
2 2 3 4 6 6 7 7 8 8 

11
4 7 4 5 7 4 9 3 3 4 6

16
4 5 7 
3 3 4 6 

Scoring

Ràng buộc:

• Có 20% số điểm ứng với \(n = 10\) và dãy không giảm;
• Có 20% số điểm ứng với \((11 \leq n \leq 200)\);
• Có 20% số điểm ứng với \((201 \leq n \leq 10^3)\);
• 40% số điểm còn lại ứng với \((10^3 < n \leq 10^6)\).