题目描述

给定 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。有 $q$ 次询问，每次询问：

• 给定一个非负整数 $k$，你需要从 $2^{a_1}, \ldots, 2^{a_n}$ 中取出一部分（即一个子集，可以为空），使得它们的和 $\ge k$。
• 在保证和 $\ge k$ 的前提下，你需要最小化它们的和。你只需求出这个最小化的和。
• $k$ 以二进制的形式给出，具体地，以 $k = \sum_{i = 1}^{m} 2^{p_i}$ 的形式给出，保证 $p_i$ 均为非负整数且严格单调递减，即 $p_i > p_{i + 1}$。

由于答案可能很大，你只需要输出对 $998244353$ 取模后的结果。

若无法从 $2^{a_1}, \ldots, 2^{a_n}$ 中取出一部分使得它们的和 $\ge k$，该询问输出 $-1$。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行第一个非负整数为 $m$，接下来 $m$ 个非负整数为 $p_1,p_2,\dots,p_m$，表示询问的 $k=\sum_{i=1}^m 2^{p_i}$。保证 $p_i$ 严格单调递减，即 $p_i>p_{i+1}$。

输出格式

共 $q$ 行，每行一个整数，表示答案对 $998244353$ 取模后的结果，或输出 $-1$ 表示无解。

3 3
0 0 1
0
2 1 0
1 3

0
3
-1

见下发文件。

见下发文件。

提示

【样例解释 1】

每个 $2^{a_i}$ 分别为 $1, 1, 2$。三次询问的 $k$ 为：$0,3,8$。具体如下：

• $k = 0$：取空。
• $k = 3$：取 $1, 2$ 即可。
• $k = 8$：无解。

【样例解释 2】

此样例满足子任务 $1$ 的限制。

【数据范围】

本题使用子任务捆绑测试。

对于 $100\%$ 的数据，$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}$。

表格留空表示无额外限制。

由于本题输入量较大，我们在下发文件中提供了 fast_read.cpp 可以选择使用（注意在 C++98 标准下可能无法编译通过）。

保证时间限制达到了没有使用特殊的读入优化的 std 的两倍。