The k-Dimensional Game

Two players, A and B, play an interesting game in a k-dimensional space. The space is a hypercube of size (2\times2\times\cdots\times2) (with (k) factors), where the smallest node has coordinates ((0,0,\ldots,0)) and the largest node ((1,1,\ldots,1)). Each node’s coordinates can be encoded as a binary number; for example, the coordinate ((0,1,1,1,0,0,1,0)) is encoded as (\tt 01110010), which equals (114) in decimal.

Player A and player B each initially receive a point in the space. They take turns to operate (with A going first). A dimension is defined as "operable" if and only if on that dimension at least one of the two points has a coordinate equal to (1) (i.e. not (0)). In a move, the current player may choose any operable dimension and set the coordinate of both points in that dimension to (0). A move is legal only if in the chosen dimension at least one of the points is nonzero. The players are both optimal, and the player who cannot move loses.

Notice that every coordinate is binary so that in each dimension, once a move is made the coordinate becomes (0) and no further move is available on that dimension. In other words, if we define for two points (A) and (B) their game value as (f(A,B)=\mathrm{popcount}(A,\texttt{|},B)) (where (\mathrm{popcount}) counts the number of ones in the binary representation), then the total number of available moves is (f(A,B)) and since players alternate moves, A wins the game if (f(A,B)) is odd, and B wins if (f(A,B)) is even (also, if (f(A,B)=0), A loses immediately because she cannot move).

The game is played for (q) rounds. In each round the positions of the two points are generated at random. The probability that a point is generated with a coordinate (when encoded as a number) equal to (x) is provided as (p_x). Before the game begins each round, player A chooses a playable region ([l,r]). However, if A’s initial coordinate (its encoded value) is (\textbf{not}) in ([l,r]), then A loses immediately (this rule does not apply to player B).

For the (i)th round, the playable region is ([l_i,r_i]). Player B asks (a_i) queries. In each query, her point is fixed to a coordinate whose encoded value is (x) while A’s point is drawn from the distribution defined by (p). For each query, you are to compute the winning probability of player B modulo (998244353).

Formally, for a given query with parameter (x) and playable region ([l,r]), let the probability distribution for A’s coordinate be given by (p_y) (for (0 \le y \lt 2^k)), and let the total probability mass be (P=\sum_{y=0}^{2^k-1}p_y). Then player B’s win probability is given by [ \frac{\displaystyle \sum_{\substack{y,\not\in,[l,r]}} p_y ; + ; \sum_{\substack{y\in [l,r]\ \mathrm{popcount}(x,\texttt{|},y)\equiv 0; (\bmod;2)}} p_y}{P} \quad (\bmod;998244353). ]

All answers should be computed modulo (998244353).

inputFormat

The input begins with two integers (k) and (q) (the dimension and the number of rounds). Then follows (2^k) integers: (p_0, p_1,\ldots,p_{2^k-1}) representing the weight (or probability numerator) of each coordinate. It is guaranteed that (P=\sum_{x=0}^{2^k-1}p_x > 0).

Then for each of the (q) rounds, the input is given as follows:

• A line containing three integers: (l), (r) (with (0\le l\le r<2^k)) and (m), the number of queries in this round.
• Then (m) lines follow, each containing a single integer (x) ((0\le x<2^k)), representing a query for player B’s point.

It is guaranteed that the sum of (m) over all rounds does not exceed a reasonable limit.

outputFormat

For each query (in the order given in the input), output a single line containing one integer – the winning probability of player B modulo (998244353). Note that when computing the probability, you must divide by (P) (the sum of all (p_x)), which requires using the modular inverse modulo (998244353).

sample

2 1
1 1 1 1
1 2 2
1
2

249561089
249561089