Bài tập

Tại thành phố công nghệ cao BKNation, tỷ phú BK tổ chức một cuộc thi đào mỏ dành cho \(n\) robot tinh nhuệ do anh phát triển. Mỗi robot \(i\) được trang bị một bộ khoan với sức mạnh \(a_i\) (là một số nguyên dương).

Trong phần thi "Đào mỏ đồng đội", các robot được xếp thành một hàng thẳng. Ban tổ chức yêu cầu chọn ra một đoạn liên tiếp từ vị trí \(l\) đến \(r\) \((1 \le l \le r \le n)\) sao cho:

• Tồn tại một robot thủ lĩnh tại vị trí \(j\) \((l \le j \le r)\), và
• Mọi robot trong đoạn từ \(l\) đến \(r\) đều có sức khoan chia hết cho sức khoan của thủ lĩnh.

Các robot có thể tạo nhiều tổ đội khác nhau, nhưng BK chỉ quan tâm đến những tổ đội có khoảng cách \(r - l\) lớn nhất (độ dài đội hình lớn nhất trừ đi 1).

Nhiệm vụ của bạn: Hãy tìm tất cả các chỉ số \(l\) thỏa mãn điều kiện tổ đội như trên và có \(r - l\) là lớn nhất. In ra tổng số tổ đội hợp lệ như vậy, độ dài lớn nhất \(r - l\), và danh sách các chỉ số \(l\) tương ứng theo thứ tự tăng dần.

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \le n \le 5 \cdot 10^5)\) --- số lượng robot.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) --- sức khoan của từng robot.

Output

• Dòng đầu tiên in ra hai số nguyên \(k\) và \(d\) --- số lượng tổ đội hợp lệ và độ dài lớn nhất \(r - l\).
• Dòng thứ hai in ra \(k\) số nguyên --- các chỉ số \(l\) tương ứng, theo thứ tự tăng dần.

Example

5
4 6 9 3 6

1 3
2 

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 1000\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(a_i = 2^k\).
• \(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.

"Trong thế giới nhị phân đầy ma thuật, tồn tại một chàng số nguyên tên Zero. Chàng ta có 32 bit nhưng ban đầu tất cả đều... ngủ đông (toàn số 0). Nhiệm vụ của bạn là đánh thức các bit này bằng phép thuật!"

Cho số nguyên không âm 32-bit, khởi đầu tất cả bit đều là 0. Bạn cần xử lý \(q\) phép thuật thuộc các loại sau:

• 1 k - Bùa đánh thức: Bật bit thứ \(k\) (1 \(\leq\) k \(\leq\) 31) lên thành 1
• 2 k - Bùa ngủ đông: Tắt bit thứ \(k\) về 0
• 3 k - Bùa nghịch ngợm: Đảo bit thứ \(k\) (0 thành 1, 1 thành 0)

Hãy xác định số nguyên này sau mỗi truy vấn.

Input

• Dòng đầu: Số nguyên \(q\) (\(1\) \(\leq\) \(q\) \(\leq\) \(10^5\))
• \(q\) dòng tiếp theo, mỗi dòng gồm loại phép thuật và vị trí bit \(k\) (\(0\) \(\leq\) \(k\) \(\leq\) \(31\))

Output

• Sau mỗi phép thuật, in ra giá trị thập phân của số nguyên

Example

5
1 0
1 1
2 0
3 1
3 3

1
3
2
0
8

Công ty WooHome vừa nhập khẩu \(N\) cột gỗ có chiều cao lần lượt là \(A_1, A_2, \dots, A_N\).
Công ty có \(M\) mẫu thiết kế nhà; mẫu thứ \(i\) \((1 \le i \le M)\) cần đúng \(S_i\) cột gỗ để làm cột trụ cho một ngôi nhà.
Với mỗi ngôi nhà được đặt hàng theo một trong \(M\) mẫu, công ty có lợi nhuận cố định là \(P\).

Tuy nhiên, các cột gỗ dùng trong một ngôi nhà có thể không đều nhau. Chi phí để khắc phục sự không đồng đều là

trong đó \(C\) là hệ số giá thành thi công, \(\max\) và \(\min\) lần lượt là chiều cao lớn nhất và nhỏ nhất trong các cột gỗ dùng cho ngôi nhà đó.

Vì vậy, lợi nhuận dự kiến khi thi công một ngôi nhà là

Lưu ý rằng lợi nhuận có thể âm.

WooHome muốn đáp ứng trước các đơn đặt hàng sao cho mỗi mẫu nhà có ít nhất một ngôi nhà được thi công,
và mỗi cột gỗ được dùng tối đa một lần (có thể có cột không dùng).

Hãy tìm tổng lợi nhuận dự kiến lớn nhất.

\InputFile
Dòng đầu chứa bốn số nguyên dương \(N, M, P, C\).

Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).

Dòng thứ ba chứa \(M\) số nguyên dương \(S_1, S_2, \ldots, S_M\).

\OutputFile
In ra một số nguyên là tổng lợi nhuận dự kiến lớn nhất.

Ràng buộc

• \(N \le 10^5\), \(M \le 6\), \(P \le 10^9\), \(C \le 10^6\).
• \(A_i \le 10^6\).
• \(2 \le S_i \le N\).
• \(\sum_{i=1}^{M} S_i \le N\).

\Scoring

• Subtask 1 (25%): \(N \le 10\), \(M = 1\).
• Subtask 2 (25%): \(N \le 1000\), \(M = 1\), \(S_1 = 2\).
• Subtask 3 (25%): \(M = 2\).
• Subtask 4 (25%): không có ràng buộc thêm.

Example

10 2 11 1
14 5 6 4 4 4 7 8 9 1
4 2

30

4 1 7 2
8 5 4 7
3

-11

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\)