Background

The difference from the Easy Version is that the input consists of sequences rather than strings, the input/output format is different, and the data scale is different.

Problem Description

Fusu has been awake for $36$ hours to write a Theory of Computation final project.

To be able to sleep sooner, Fusu found $n$ references. The $i$-th reference is a sequence $a_i$, and she plans to combine these references.

Specifically, there are two types of operations:

• 1 x y: Concatenate the whole sequence $a_x$ to the end of $a_y$, then delete $a_x$.
• 2 x y: Query whether $a_x$ and $a_y$ are similar.

We guarantee that after an operation 1 x y occurs, the sequence $a_x$ will not appear in any subsequent operations. That is, operation type $1$ occurs at most $n - 1$ times.

The definition of similar is: for two sequences $a_x$ and $a_y$, if there exists a way to reorder $a_x$ such that the reordered $a_x$ is equal to $a_y$, then $a_x$ and $a_y$ are called similar.

For example, suppose $a_1 = 1,2$, $a_2 = 3,4$, and $a_3 = 1,2,3,4$. After executing 1 1 2, $a_1$ is deleted, and $a_2 = 3,4,1,2$, while $a_3 = 1,2,3,4$. Continuing with 2 2 3, since we can reorder $a_2$ into $1,2,3,4$, $a_2$ and $a_3$ are similar.

Note that operation type $2$ does not actually modify any sequence.

Input Format

The first line contains two integers, denoting the number of references $n$ and the number of operations $q$.
The next $n$ lines each describe a sequence. Line $i$ describes $a_i$:
the first number is $m_i$, the length of $a_i$, followed by $m_i$ numbers describing the sequence $a_i$.
The next $q$ lines each contain three integers $op, x, y$, with meanings as described in the Description.

Output Format

To avoid excessive output, output one line with one integer, denoting the bitwise XOR of the operation indices of all queries whose answer is the two sequences are similar.

Operation indices start from $1$. Both types of operations increase the index by $1$. You may refer to the sample explanation to understand the output format.

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

Hint

Sample Explanation

There are five operations in total. Their indices and answers are as follows: | Index | Operation | Answer | | :-: | :-: | :-: | | $1$ | 1 1 2 | Not a query operation | | $2$ | 2 2 3 | Similar | | $3$ | 2 3 4 | Not similar | | $4$ | 2 2 4 | Not similar | | $5$ | 2 2 3 | Similar |

We can see that the operation indices of queries answered the two sequences are similar are $2$ and $5$. Their bitwise XOR is $7$. Therefore, the output is $7$.

Constraints and Notes

For all test points, it is guaranteed that $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$. All elements in the sequences are non-negative integers not exceeding $10^9$.

The testdata guarantees that the elements are generated in the following way: for a sequence, an upper bound $k$ on the element values is specified, then $m_i$ integers are generated uniformly at random in $[0, k]$ as the sequence $a_i$. Note that $k$ is not necessarily $10^9$.

Translated by ChatGPT 5