Problem Description

Given \( n \) non-negative integers \( a_1, a_2, \ldots, a_n \). There are \( q \) queries, each query:

• Given a non-negative integer \( k \), you need to select a subset (which can 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 their sum. You only need to find this minimized sum.
• \( k \) is given in binary form, specifically, in the form \( k = \sum_{i = 1}^{m} 2^{p_i} \), where \( p_i \) are non-negative integers and strictly monotonically 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 not possible to select a subset 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 \) and \( q \).

The second line contains \( n \) non-negative integers \( a_1, a_2, \ldots, a_n \).

The next \( q \) lines, each line starts with a non-negative integer \( m \), followed by \( m \) non-negative integers \( p_1, p_2, \ldots, p_m \), representing the query \( k = \sum_{i = 1}^m 2^{p_i} \). It is guaranteed that \( p_i \) are strictly monotonically decreasing, i.e., \( p_i > p_{i + 1} \).

Output Format

Output \( q \) lines, each line containing an integer representing the result modulo \( 998244353 \), or output \(-1\) if there is no solution.

Sample Input and Output

Sample Input #1

3 3
0 0 1
0
2 1 0
1 3

Sample Output #1

0
3
-1

Sample Input #2

See the provided file.

Sample Output #2

See the provided file.

Notes/Hints

[Sample Explanation 1]

Each \( 2^{a_i} \) is \( 1, 1, 2 \). The \( k \) values for the three queries are: \( 0, 3, 8 \). Specifically:
- \( k = 0 \): Select an empty set.
- \( k = 3 \): Select \( 1, 2 \).
- \( k = 8 \): No solution.

[Sample Explanation 2]

This sample satisfies the constraints of Subtask 1.

[Data Range]

This problem uses subtask-based testing.

For \( 100\% \) of the data, \( 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 \), \( p_i > p_{i + 1} \).

The table is left blank indicating no additional restrictions.

Due to the large input size, we have provided fast_read.cpp in the provided file which you can choose to use (note that it may not compile under C++98 standard).

The time limit is guaranteed to be twice that of the standard solution without special input optimizations.

见题面 Input 部分

见题面 Output 部分