题目描述

有 $n$ 个人，第 $i$ 个人有一个目标值 $a_i$，还有 $k_i$ 个数对，第 $j$ 个数对是

$$(x_{i,j},y_{i,j}).$$

现在要进行 $q$ 次操作：

1. 1 x v：将 $a_x$ 修改为 $v$。
2. 2 l r v：表示区间 $[l,r]$ 内的人从左到右依次对 $v$ 进行操作。每个人都必须使用他的每个数对恰好一次，即对于所有 $1\le j\le k_i$，将 $v$ 变为 $v\oplus x_{i,j}$ 或者 $v\oplus y_{i,j}$。

每个人都知道全部信息，包括别人的所有数对和别人的目标值，并且都绝顶聪明。每个人都希望 $v$ 的终值和自己的目标值的异或值尽量小。对于每个操作 2，求出 $v$ 的终值。

输入格式

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

接下来一行 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示每个人的目标值。

接下来 $n$ 行，第 $i$ 行表示第 $i$ 个人的信息：

• 先读入非负整数 $k$，表示该人拥有的数对个数；
• 接下来读入 $2k$ 个非负整数，依次表示

$$x_{i,1},y_{i,1},x_{i,2},y_{i,2},\ldots,x_{i,k},y_{i,k}.$$

接下来 $q$ 行，每行若干个非负整数，表示一次命令。

输出格式

为了减少输出量，你需要维护一个 unsigned long long 变量 $ans$，初值为 $0$。遇到一次查询操作时，令

$$ans\leftarrow 131\times ans+v,$$

其中 $v$ 是本次查询的答案。

所有操作处理完毕后，输出最终的 $ans$。

样例 1 输入

5 7
3 3 17 6 15
2 9 14 21 3
1 20 13
3 12 6 26 23 1 4
0
1 16 9
1 1 16
2 3 4 17
1 3 1
2 3 3 31
2 3 3 17
2 4 5 19
1 1 2

样例 1 输出

2248225

样例 1 解释

查询答案依次为 $1,0,1,3$。

更多样例见下发文件。

数据范围

对于所有测试数据，保证：

$$1\le n\le 5\times 10^5, \qquad 1\le q\le 10^6.$$

令 $M$ 为 $v,x,y$ 的位数，$m=\sum k_i$。

子任务	$n$	$M$	$m$	$q$	特殊性质	分数
1	$\le 100$	$\le 6$	$\le 300$	$\le 100$	A	10
2		$\le 64$				15
3	$\le 10^5$		$\le 2\times 10^5$		B	10
4					C
5					D
6					无	15
7	$\le 5\times 10^5$		$\le 10^6$			30

特殊性质：

• A：保证数据随机。
• B：保证 $a_i$ 全相同且没有修改操作。
• C：保证没有修改操作。
• D：保证操作 2 满足 $l=r$。