P8496 [NOI2022] Majority Element.

**For a sequence, define its majority element as a number whose occurrence count is strictly greater than half of the sequence length. Note that this definition differs from the usual one. In this problem, please follow the definition given here.** Initially, you are given $n$ positive-integer sequences with different lengths, numbered $1 \sim n$. An initial sequence may be empty. These $n$ sequences are considered to exist, and sequences with other indices are considered nonexistent. There are $q$ operations 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 last number of sequence $x$. It is guaranteed that sequence $x$ exists and is non-empty, and $1 \le x \le n + q$. - $3 \ m \ x_1 \ x_2 \dots \ x_m$: Concatenate sequences $x_1, x_2, \ldots, x_m$ in order to obtain a new sequence, and query its majority element. If there is no number satisfying the condition above, output $-1$. The testdata guarantees that for any $1 \le i \le m$, $x_i$ is a sequence that still exists, $1 \le x_i \le n + q$, and the concatenated sequence is non-empty. **Note: $\boldsymbol{x_1, \ldots, x_m}$ are not guaranteed to be distinct, and the merge operation in a query does not affect subsequent operations.** - $4 \ x_1 \ x_2 \ x_3$: Create a new sequence with index $x_3$, which is the result of appending all numbers of sequence $x_2$ to the end of sequence $x_1$ in order, and then delete sequences $x_1$ and $x_2$. After that, sequence $x_3$ is considered to exist, while sequences $x_1$ and $x_2$ are considered nonexistent 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_2$, sequences $x_1$ and $x_2$ exist before the operation, and no sequence has used index $x_3$ before this operation.

The first line contains two positive integers $n$ and $q$, representing the number of sequences and the number of operations. It is guaranteed that $n \le 5 \times {10}^5$ and $q \le 5 \times {10}^5$. The next $n$ lines describe the sequences. On line $i$, the first non-negative integer $l_i$ denotes the number of elements in the initial sequence $i$. Then follow $l_i$ non-negative integers $a_{i,j}$ in order, representing the elements in the sequence. Let $C_l = \sum l_i$ be the total length of all input sequences. It is guaranteed that $C_l \le 5 \times {10}^5$ and $a_{i,j} \le n + q$. The next $q$ lines each contain several positive integers describing one operation, given in the format specified in the statement. Let $C_m = \sum m$ be the total number of sequences to be concatenated across all type $3$ operations. It is guaranteed that $C_m \le 5 \times {10}^5$.

For each query, output one integer per line as the corresponding answer.

**[Sample Explanation \#1]** The first query asks for the majority element of sequence $1$. Since the sequence contains two $1$'s, which is more than half of the sequence length, the majority element is $1$. The second query asks for the majority element of sequence $2$. Since the sequence contains only $3$, the majority element is $3$. The third query asks for the majority element of sequence $3$. At this time, sequence $3$ is $(3, 3, 3, 1, 1, 2)$. There is no number that appears more than $3$ times, so output $-1$. ---- **[Sample Explanation \#2]** The first query asks for the majority element of the sequence obtained by concatenating sequences $1, 2, 3, 4$. The result is $(1, 2, 3, 4)$. There is no number that appears more than twice, so output $-1$. The fourth query asks for the majority element of the sequence obtained by concatenating sequences $1, 2, 3, 4$. The result is $(1, 2, 2, 4, 4, 4, 4)$, and the majority element is $4$. ---- **[Sample \#3]** See `major/major3.in` and `major/major3.ans` in the attachment. This sample satisfies the constraints of test points $1 \sim 3$. ---- **[Sample \#4]** See `major/major4.in` and `major/major4.ans` in the attachment. This sample satisfies the constraints of test points $11 \sim 12$. ---- **[Constraints]** For all test data, it is guaranteed that $1 \le n, q, C_m, C_l \le 5 \times {10}^5$. | $n, q$ | $C_m, C_l$ | Test Point IDs | Special Property A | Special Property B | Special Property C | |:-:|:-:|:-:|:-:|:-:|:-:| | $\le 300$ | $\le 300$ | $1 \sim 3$ | No | No | Yes | | $\le 4000$ | $\le 4000$ | $4 \sim 7$ | No | No | Yes | | $\le {10}^5$ | $\le {10}^5$ | $8$ | Yes | Yes | Yes | | $\le {10}^5$ | $\le {10}^5$ | $9$ | Yes | No | No | | $\le {10}^5$ | $\le {10}^5$ | $10$ | No | Yes | No | | $\le {10}^5$ | $\le {10}^5$ | $11 \sim 12$ | No | No | Yes | | $\le {10}^5$ | $\le {10}^5$ | $13$ | No | No | No | | $\le 5 \times {10}^5$ | $\le 5 \times {10}^5$ | $14$ | Yes | Yes | Yes | | $\le 5 \times {10}^5$ | $\le 5 \times {10}^5$ | $15$ | Yes | No | No | | $\le 5 \times {10}^5$ | $\le 5 \times {10}^5$ | $16$ | No | Yes | No | | $\le 5 \times {10}^5$ | $\le 5 \times {10}^5$ | $17 \sim 18$ | No | No | Yes | | $\le 5 \times {10}^5$ | $\le 5 \times {10}^5$ | $19 \sim 20$ | No | No | No | Special Property A: It is guaranteed that $n = 1$ and there is no operation of type $4$. Special Property B: It is guaranteed that at any time, every sequence contains only the numbers $1$ and $2$. Special Property C: It is guaranteed that there is no operation of type $2$. Translated by ChatGPT 5