30383번 - Major 다국어

문제

In this problem, the mode of a sequence is the number that appears strictly more than half the times in the sequence. Please refer to this definition in the problem.

Initially, $n$ positive integer sequences of different lengths are given, numbered from 1ドル$ to $n,ドル and the sequences can be empty. These $n$ sequences are considered to exist, and the sequences corresponding to other numbers are considered to be non-existent.

There are $q$ operations, and operations are of the following types:

• 1ドル\ x\ y$: Insert the number $y$ at the end of sequence $x$. It is guaranteed that sequence $x$ exists and 1ドル \le x, y \le n + q$.
• 2ドル\ x$: Delete the number at the end of sequence $x$. It is guaranteed that sequence $x$ exists, is not empty, and 1ドル \le x \le n + q$.
• 3ドル\ m\ x_1\ x_2\ ...\ x_m$: Concatenate sequences $x_1, x_2, \ldots, x_m$ to get a new sequence and return its mode. Return -1 if the mode does not exist. The data guarantees that for any 1ドル \le i \le m$ the sequence numbered $x_i$ still exists, 1ドル \le x_i \le n + q,ドル and the concatenated sequence is non-empty. There is no guarantee that $x_i$ are distinct. The concatenation done here won't affect future operations.
• 4ドル\ x_1\ x_2\ x_3$: Create a new sequence numbered $x_3,ドル which is the concatenation of sequence $x_1$ and sequence $x_2$. Then, delete the sequences numbered $x_1$ and $x_2$. After this operation, sequence $x_3$ is considered to exist, and the sequences $x_1$ and $x_2$ are considered to be non-existent and will not be used again in subsequent operations. It is guaranteed that 1ドル \le x_1, x_2, x_3 \le n + q,ドル $x_1 \ne x_1,ドル the sequences $x_1$ and $x_2$ existed before the operation, and no operation used the sequence numbered $x_3$ before the operation.

입력

The first line of input contains two positive integers $n$ and $q,ドル which represent the number of initial sequences and the number of operations, respectively. It is guaranteed that $n, q \le 5 \times 10^5$.

In the next $n$ lines, the $i$-th line represents the sequence numbered $i$. The first non-negative integer $l_i$ of each line represents the length of the $i$-th sequence, followed by $l_i$ non-negative integers $a_{i,j}$ representing the elements of the sequence in order. Let $C_l = \Sigma l_i$ represent the sum of the input sequence lengths, then it is guaranteed that $C_l \le 5 \times 10^5$ and $a_{i,j} \le n + q$.

Each of the next $q$ lines represent an operation in the format described above, consisting of several integers. Let $C_m = \Sigma m$ represent the sum of all sequences that need to be concatenated in operation 3, then it is guaranteed that $C_m \leq 5 \times 10^{5}$.

출력

For each type 3 query, output an integer on a new line, the answer to the query.

제한

For all test data, it is guaranteed that 1ドル \le n, q, C_m, C_l \le 5 \times 10^{5}$.

힌트

추가 예제

samples.zip