Bài tập

Nam có \(N\) đồng tiền được đánh số từ \(1\) đến \(N\), đồng tiền thứ \(i\) có mệnh giá là \(T_i\) (\(1 \le i \le N\)).

Siêu thị có \(M\) mặt hàng được đánh số từ \(1\) đến \(M\), mặt hàng thứ \(j\) được bán với giá là \(P_j\) (\(1 \le j \le M\)).

Yêu cầu: Hãy xác định với mỗi mặt hàng trong siêu thị Nam có thể sử dụng các đồng tiền hiện có của mình để mua được hay không với điều kiện là trả đúng giá và không lấy lại tiền thối.

Input

• Dòng đầu ghi số nguyên dương \(N\) và \(M\);
• Dòng thứ hai ghi \(N\) số nguyên dương \(T_1,T_2,...,T_N\);
• Dòng thứ ba ghi \(M\) số nguyên dương \(P_1,P_2,...,P_M\);
• Các số có giá trị không quá \(10^6\) và được ghi cách nhau ít nhất một dấu cách.

Output

• Gồm \(M\) dòng ghi kết quả tương ứng của từng mặt hàng: YES nếu có
  thể mua được, ngược lại ghi NO.

Example

3 4
1 2 6
1 2 3 5

YES
YES
YES
NO

Scoring

• Có \(50\%\) số điểm \(N \le 15\) và \(M \le 100\);
• Có \(50\%\) số điểm \(15 < N \le 20\) và \(M \le 100 000\).

Trong triển lãm hội họa có \(N\) bức tranh được chuyển đến, bức tranh thứ \(i\) có độ thẩm mĩ là \(A_i\) (\(1 \le A_i \le 10^9\)). Ban tổ chức muốn chọn ra 3 bức tranh thứ \(x, y\) và \(z\) trưng bày ở trung tâm sao cho \(A_x = P, A_y = Q, A_z = R\) và \(1 \le x < y < z \le N\).

Yêu cầu: Hãy lập trình giúp Ban tổ chức đếm số cách khác nhau có thể chọn được. Biết rằng hai cách khác nhau khi có ít nhất một bức tranh được chọn khác nhau.

Input

• Dòng đầu ghi số nguyên dương \(N\).
• Dòng thứ hai ghi lần lượt \(N\) số nguyên \(A_1, A_2, \ldots, A_N\).
• Dòng thứ ba ghi 3 số nguyên \(P, Q\) và \(R\) (\(1 \le P, Q, R \le 10^9\)).
• Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số duy nhất là số cách tìm được.

Example

5
1 2 2 1 2
1 2 1

2

Scoring

• Có 30% số điểm tương ứng \(3 \le N \le 200\);
• Có 30% số điểm tương ứng \(200 < N \le 30000\);
• Có 40% số điểm tương ứng \(30000 < N \le 2000000\).

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