Description

For a sequence, the majority element of it is defined as the number whose occurrence is strictly more than half the size of the sequence. This is different from the mode of a sequence. Please refer to this definition in this problem.

You're given $n$ positive integer sequences of varying length, labeled by $1 \sim n$. The initial sequence may be empty. These $n$ sequences exist while sequences labelled by other numbers are deemed non-existent.

There are $q$ operations of following types:

• $1\, x\, y$: Insert number $y$ at the end of sequence $x$. It is guaranteed that sequence $x$ exists, and $1 \leq x,y \leq n+q$.

• $2\, x$: Remove the last number from sequence $x$. It is guaranteed that sequence $x$ exists, is non-empty, and $1 \leq x \leq n+q$.

• $3\, m\, x_1\, x_2\, \ldots\, x_m$: Concatenate sequences $x_1,x_2,\ldots,x_m$ in order into a new sequence and query its majority element. If no such number exists, return $-1$. It is guaranteed that sequence $x_i$ still exists for any $1 \leq i \leq m$, $1 \leq x_i \leq n+q$, and the resulting sequence is non-empty. Note: it is not guaranteed that $\boldsymbol{x_1,x_2,\ldots,x_m}$ are distinct, and the combining operation in this query has no effect on following operations.

• $4\, x_1\, x_2\, x_3$: Create a new sequence $x_3$ as the result of successively inserting numbers in sequence $x_2$ to the end of sequence $x_1$, then remove the sequences corresponding to numbers $x_1,x_2$. At this time sequence $x_3$ is deemed existent, sequence $x_1,x_2$ don't exist and won't be used in following operations. It is guaranteed that $1 \leq x_1,x_2,x_3 \leq n+q$, $x_1 \neq x_2$, sequences $x_1,x_2$ exist before this operation, and sequence $x_3$ is not used by any preceding operations.

Input Format

Read from file major.in.

The first line of input contains two integers $n$ and $q$, each indicating the number of sequences and operations. It is guaranteed that $n \leq 5 \times 10^5$, $q \leq 5 \times 10^5$.

For the following $n$ lines, the $i$th line corresponds to sequence $i$. Each line begins with a non-negative integer $l_i$ indicating the number count of the initial $i$th sequence. Following are $l_i$ nonnegative numbers $a_{i,j}$ representing the numbers in the sequence in order. Suppose $C_l = \sum\ l_i$ is the sum of length of the inputted sequences, then it is guaranteed that $C_l \leq 5 \times 10^5$, $a_{i,j} \leq n+q$.

Each of the following $Q$ lines consists of several integers representing an operation, formatted as stated in the description.

Suppose $C_m = \sum m$ is the sum of number of sequences to be concatenated in all type $3$ operations, then it is guaranteed that $C_m \leq 5 \times 10^5$.

Output Format

Output to file major.out.

For each query, output a line of one integer indicating the corresponding answer.

2 8
3 1 1 2
3 3 3 3
3 1 1
3 1 2
4 2 1 3
3 1 3
2 3
3 1 3
1 3 1
3 1 3

1
3
-1
3
-1

4 9
1 1
1 2
1 3
1 4
3 4 1 2 3 4
1 1 2
3 2 1 2
2 3
3 3 1 2 3
1 4 4
1 4 4
1 4 4
3 4 1 2 3 4

-1
2
2
4

Sample 3

See files [major3.in](file://major3.in) and [major3.ans](file://major3.ans) in the attachment. This sample satisfies the constraints of tests $1 \sim 3$.

Sample 4

See files [major4.in](file://major4.in) and [major4.ans](file://major4.ans) in the attachment. This sample satisfies the constraints of tests $11 \sim 12$.

Constraints and Hint

For all the tests, $1 \leq n,q,C_m,C_l \leq 5 \times 10^5$.

Special case A: It is guaranteed that $n = 1$ and there's no type $4$ operation.

Special case B: It is guaranteed that at any time and in any sequence there are only numbers $1$ and $2$.

Special case C: It is guaranteed that there's no type $2$ operation.