P10675 [MX-S1-T4] Foresight.

Original problem link: 。

You are given $n$ non-negative integers $a_1, a_2, \ldots, a_n$。There are $q$ queries, and for each query: - Given a non-negative integer $k$, you need to pick some elements (i.e., a subset, which may be empty) from $2^{a_1}, \ldots, 2^{a_n}$ such that their sum is $\ge k$。 - Under the condition that the sum is $\ge k$, you need to minimize the sum. You only need to output this minimized sum. - $k$ is given in binary form. Specifically, it is given in the form $k = \sum_{i = 1}^{m} 2^{p_i}$, and it is guaranteed that all $p_i$ are non-negative integers and strictly decreasing, i.e., $p_i > p_{i + 1}$。 Since the answer may be very large, you only need to output the result modulo $998244353$。 If it is impossible to pick some elements from $2^{a_1}, \ldots, 2^{a_n}$ such that their sum is $\ge k$, output $-1$ for that query.

The first line contains two positive integers $n, q$。 The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$。 The next $q$ lines describe the queries. Each line starts with a non-negative integer $m$, followed by $m$ non-negative integers $p_1, p_2, \dots, p_m$, representing $k = \sum_{i = 1}^{m} 2^{p_i}$。It is guaranteed that $p_i$ are strictly decreasing, i.e., $p_i > p_{i+1}$。

Output $q$ lines. Each line contains one integer, the answer modulo $998244353$, or $-1$ if there is no solution.

__Sample Explanation 1__ Each $2^{a_i}$ is $1, 1, 2$ respectively. The values of $k$ in the three queries are: $0, 3, 8$. Details: - $k = 0$: choose the empty set. - $k = 3$: choosing $1, 2$ is enough. - $k = 8$: no solution. __Sample Explanation 2__ This sample satisfies the constraints of Subtask $1$。 __Constraints__ __This problem uses bundled subtasks for judging.__ For $100\%$ of the testdata, $1 \le n, q \le 10^6$, $0 \le m \le 10^6$, $\sum m \le 5 \times 10^6$, $0 \le a_i, p_i \le 10^6$, and $p_i > p_{i+1}$。 Blank entries in the table mean there are no additional constraints. | Subtask ID | $n \le$ | $q \le$ | $\sum m \le$ | $a_i, p_i \le$ | Special Property | Score | | ---------- | -------------- | -------------- | ---------------- | -------------- | ----------------------- | ----- | | $1$ | $20$ | | | $60$ | | $10$ | | $2$ | $120$ | | | $60$ | | $10$ | | $3$ | $5\times 10^3$ | $5\times 10^3$ | $2.5\times 10^4$ | $5\times 10^3$ | | $20$ | | $4$ | $10^5$ | $10^5$ | $5\times 10^5$ | $10^5$ | | $20$ | | $5$ | | | | | $m \le 2$ | $10$ | | $6$ | | | | | All $a_i$ are distinct. | $10$ | | $7$ | $10^6$ | $10^6$ | $5\times 10^6$ | $10^6$ | | $20$ | Since the input size is large, we provide `fast_read.cpp` in the attached files for optional use (note that it may fail to compile under the C++98 standard). It is guaranteed that the time limit is set to twice that of using standard `std` input without special input optimizations. Translated by ChatGPT 5