問題文

Mitsubachi 君は全部で $N$ 日間の卒業旅行を計画しています。
Mitsubachi 君は $1$ 日目が始まる前は地点 $0$ にいます。
この旅行のあいだ Mitsubachi 君は長さ $N$ の整数列 $A_1, A_2 ,\ ...\ , A_N$ に従って移動することにしました。
$i$ 日目では整数 $A_i$ を使うか使わないかを決め、使う場合は現在の位置を地点 $j$ とすると地点 $j\ {\rm XOR}\ A_i$ に移動し、使わない場合はその場所にとどまります。
ただし移動の結果、場所が変わらなかった場合も、移動したとして扱うことにします。
$Q$ 個のクエリが与えられるので、それらに答えてください。$i$ 番目のクエリは以下の内容です。

長さ $M_i$ の整数列 $B_{i1}, B_{i2} ,\ ...\ , B_{iM_i}$ が与えられる。
$B_{i1}, B_{i2} ,\ ...\ , B_{iM_i}$ 日目と $N$ 日目を終えた時、それぞれすべてで地点 $0$ にいるような $N$ 日間の行動の仕方は何通りか。

入力

$N\ \ Q$
$A_1\ \ A_2\ \cdots\ A_N$
$M_1$
$B_{11}\ \ B_{12}\ \cdots\ B_{1M_1}$
$M_2$
$B_{21}\ \ B_{22} \ \cdots\ B_{2M_2}$
$\ \vdots$
$M_Q$
$B_{Q1}\ \ B_{Q2} \ \cdots\ B_{QM_Q}$

入力はすべて整数
$ 2 \leq N \leq 10^4$
$ 1 \leq Q \leq 10^4$
$ 0 \leq A_i < 2^{32}\ \ (1 \leq i \leq N)$
$ 1 \leq M_i \leq {\rm min}(N-1,\ 10)\ \ (1 \leq i \leq Q)$
$ 1 \leq B_{ij} \leq N-1\ \ (1\leq i \leq Q,\ 1\leq j \leq M_i)$
$ B_{ij} < B_{ij+1}\ \ (1\leq i \leq Q,\ 1\leq j < M_i)$

出力

クエリの答えを $1$ 行ずつ、合計 $Q$ 行に出力してください。 最後に改行してください。

サンプル

3 1
1 1 2
1
2

2

6 3
0 0 0 0 0 0
1
2
3
2 3 4
2
3 4

64
64
64

50 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1
3
3 19 20
9
2 3 5 7 9 11 13 17 19
4
2 7 18 28

877905026
134217728
294967268

出典

灘校75回生中学卒業記念コンテスト: Graduation Trip
writer: Mitarushi
tester: Sashiming,karudano
HackerRankの規約に基づいて移植しております。一部改変したところがあります。