P9216 [Beginner Contest #11] Writing the Final Project (Hard Version)

**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**.

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.

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**.

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.

### 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