[入门赛 #11] 写大作业 (Hard Version)

**本题与 Easy Version 的区别在于：输入的是数列而不是字符串，输入输出格式不同，数据规模不同**。

扶苏为了写计算理论大作业已经 $36$ 小时没有合眼了。 为了能快点睡觉，扶苏找到了 $n$ 份文献，第 $i$ 份文献是一数列 $a_i$，她打算把这些文献组合起来。 具体来说，一共有两种操作： - `1 x y`：把文献 $a_x$ 整体拼接到 $a_y$ 的后面，然后删除 $a_x$。 - `2 x y`：查询 $a_x$ 和 $a_y$ 是否**相似**。 我们保证在 `1 x y` 操作出现后，数列 $a_x$ **不会**出现在接下来的任何操作中。这就是说，操作 $1$ 至多有 $n-1$ 次。 **相似**的定义是：对两个数列 $a_x$ 和 $a_y$，如果存在一种重新排列 $a_x$ 的方法，使得重排后的 $a_x$ 和 $a_y$ 相等，则称 $a_x$ 和 $a_y$ **相似**。 例如，假设 $a_1 = 1,2$, $a_2 = 3,4$，$a_3 = 1,2,3,4$，则执行 `1 1 2` 后，$a_1$ 被删除，$a_2 = 3,4,1,2$，$s_3 = 1,2,3,4$；继续执行 `2 2 3` 后，因为可以把 $a_2$ 重排为 $1,2,3,4$，所以 $a_2$ 和 $a_3$ 相似。 注意，操作 $2$ 不会对数列做出实际修改。

第一行是两个整数，分别表示文献的数量 $n$ 和操作的数量 $q$。 接下来 $n$ 行，每行描述一个数列。第 $i$ 行描述 $a_i$： 每行第一个数是 $m_i$，表示数列 $a_i$ 的长度，接下来有 $m_i$ 个数，描述数列 $a_i$。 接下来 $q$ 行，每行三个整数 $op, x, y$，其含义见『题目描述』。

为了避免输出过大，请你输出一行一个整数，表示所有答案为**两数列相似**的询问的**操作编号**的按位异或和。 操作的编号从 $1$ 开始，两种操作均会令编号增加 $1$。你可以参考样例解释来理解输出格式。

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

7

### 样例解释 共有五次操作，它们的编号和回答情况如下： | 编号 | 操作 | 回答 | | :-: | :-: | :-: | | $1$ | `1 1 2` | 不是查询操作| | $2$ | `2 2 3` | 相似 | | $3$ | `2 3 4` | 不相似 | | $4$ | `2 2 4` | 不相似 | | $5$ | `2 2 3` | 相似 | 可以看到，回答为**两数列相似**的询问的操作编号为 $2$ 和 $5$。它们的按位异或和是 $7$。故输出为 $7$。 ### 数据规模与约定 对全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq q \leq 5 \times 10^6$，$1 \leq m_i \leq 10^5$，$\sum_{i = 1}^n m_i \leq 5 \times 10^5$。数列里的元素都是不超过 $10^9$ 的非负整数。 数据保证数列元素的生成方式是：对一个数列，限定一个该数列元素大小的上界 $k$，然后在 $[0, k]$ 内均匀随机地生成 $m_i$ 个整数作为数列 $a_i$。注意，$k$ 不一定是 $10^9$。