时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的非负整数数组 $a_1, a_2, \dots, a_n$。

定义一个序列 $s = [s_1, s_2, \dots, s_m]$ 的权值 $w(s)$ 为该序列中所有相邻元素对的按位异或值的和。即：

特别地，当序列长度 $m < 2$ 时，$w(s) = 0$。

现在有 $q$ 相互独立的查询。 在第 $j$ 次查询中，给定 $k_j$ 个严格递增的下标 $p_1, p_2, \dots, p_{k_j}$。你需要从原序列 $a$ 中暂时删除这些下标对应的元素。删除后，序列 $a$ 中剩余的元素将保持原有的相对顺序，拼接成一个新的序列 $a'$。

请你计算并输出每次查询后，新序列 $a'$ 的权值 $w(a')$。

格式

输入格式

第一行包含两个正整数 $n, q$，分别表示原序列的长度和查询的次数。

第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示原序列的元素。

接下来的 $q$ 行，每行首先给出一个正整数 $k_j$，随后跟着 $k_j$ 个严格递增的正整数 $p_1, p_2, \dots, p_{k_j}$，表示本次查询需要删除的元素下标。

输出格式

输出包含 $q$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 次查询的新序列权值。

样例

样例输入 #1

5 2
1 2 3 4 5
1 3
2 2 4

样例输出 #1

10
8

样例解释 #1

原序列为 $a = [1, 2, 3, 4, 5]$。

查询 $1$： 删除下标 $3$（对应数值 $3$）。 剩余序列 $a' = [1, 2, 4, 5]$。 权值 $w(a') = (1\oplus2) + (2\oplus4) + (4\oplus5) = 3 + 6 + 1 = 10$。

查询 $2$： 删除下标 $2, 4$（对应数值 $2, 4$）。 剩余序列 $a' = [1, 3, 5]$。 权值 $w(a') = (1\oplus3) + (3\oplus5) = 2 + 6 = 8$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$3 \le n \le 2\times 10^5$，$1 \le q \le 2 \times 10^5$，$0 \le a_i \le 2^{30}$，$1 \le k_j \le n$，$1 \le p_1 < p_2 < \dots < p_{k_j} \le n$，保证所有查询的 $k_j$ 的和不超过 $2\times 10^5$。