Background

Original problem link: https://oier.team/problems/S1D。

Problem Description

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.

Input Format

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 Format

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

3 3
0 0 1
0
2 1 0
1 3

0
3
-1

见下发文件。

见下发文件。

Hint

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.

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