Subset Sum Minimization with Powers of Two

You are given a multiset of coins. The coins are given indirectly by an array of non‐negative integers \(a_1, a_2, \ldots, a_n\). For each \(i\) the available coin has a value \(2^{a_i}\).

There are \(q\) queries. In each query you are given a non‐negative integer \(k\) in its binary decomposed form. Specifically, you are given an integer \(m\) and \(m\) strictly decreasing non‐negative integers \(p_1, p_2, \ldots, p_m\); it is guaranteed that \[ k = \sum_{i=1}^{m}2^{p_i}. \]

Your task for each query is to choose a subset (possibly empty) of the coins \(\{2^{a_1},\ldots,2^{a_n}\}\) such that their sum is at least \(k\). Among all such choices, you must choose one which minimizes the sum. If no subset can achieve a sum \(\ge k\) then output \(-1\); otherwise, output the minimal sum modulo \(998244353\).

Note: The coins are given as powers of two. The query target is specified by the exponents of the binary representation. Even though the coins and \(k\) may be large, there are only a few distinct coin denominations.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n\)).

The second line contains \(n\) non‐negative integers: \(a_1, a_2, \ldots, a_n\) (each representing that a coin of value \(2^{a_i}\) is available).

The third line contains a single integer \(q\) (number of queries).

Then \(q\) queries follow. For each query, the first number is an integer \(m\) (the number of terms in the binary representation of \(k\)), followed by \(m\) non‐negative integers \(p_1, p_2, \ldots, p_m\) separated by spaces. It is guaranteed that \(p_1 > p_2 > \cdots > p_m\) and \[ k = \sum_{i=1}^{m} 2^{p_i}. \]

outputFormat

For each query, output a single line containing one integer: the minimum possible sum of the chosen subset modulo \(998244353\), or \(-1\) if no such subset exists.

sample

3
1 1 0
3
2 1 0
1 2
1 3

3
4
-1