题目背景

本题与 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$。