For a sequence, its mode is defined as a number that appears strictly more than half the time in the sequence. Note that this definition differs from the standard one; please follow the definition provided in this problem.

Initially, there are $n$ sequences of varying lengths, numbered $1 \sim n$. The initial sequences may be empty. These $n$ sequences are considered to exist, while sequences with other numbers are considered not to exist.

There are $q$ operations of the following types:

• 1 x y: Append the number $y$ to 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 from sequence $x$. It is guaranteed that sequence $x$ exists and is non-empty, and $1 \le x \le n + q$.
• 3 m x1 x2 ... xm: Concatenate sequences $x_1, x_2, \dots, x_m$ in order to form a new sequence, and query its mode. If no number satisfies the condition above, return $-1$. It is guaranteed 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: It is not guaranteed that $x_1, \dots, x_m$ are distinct, and the merge operation in the query does not affect subsequent operations.
• 4 x1 x2 x3: Create a new sequence numbered $x_3$, which is the result of appending sequence $x_2$ to the end of sequence $x_1$, then delete sequences $x_1$ and $x_2$. At this point, sequence $x_3$ is considered to exist, while sequences $x_1$ and $x_2$ are considered not to exist and will not be used in subsequent operations. It is guaranteed that $1 \le x_1, x_2, x_3 \le n + q$, $x_1 \neq x_2$, sequences $x_1$ and $x_2$ exist before the operation, and no sequence has used the number $x_3$ before this operation.

Input

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

The next $n$ lines describe the sequences numbered $1$ to $n$. The first non-negative integer $l_i$ in each line represents the number of elements in the initial sequence $i$, followed by $l_i$ non-negative integers $a_{i,j}$ representing the numbers in the sequence in order. Let $C_l = \sum l_i$ be the sum of the lengths of the 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 representing an operation, formatted as described above. Let $C_m = \sum m$ be the sum of the number of sequences to be concatenated across all type 3 operations; it is guaranteed that $C_m \le 5 \times 10^5$.

Output

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

Examples

Input 1

2 8
3 1 1 2
3 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

Output 1

1
3
-1
3
-1

Note 1

The first query asks for the mode of sequence 1. Since the sequence contains two 1s, which is more than half of the sequence length, the mode is 1. The second query asks for the mode of sequence 2. Since the sequence only contains 3, the mode is 3. The third query asks for the mode of sequence 3. At this point, sequence 3 is $(1, 1, 2, 3, 3, 3)$, and there is no number that appears more than 3 times, so the output is $-1$.

Input 2

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

Output 2

-1
2
2
4

Note 2

The first query asks for the mode of the sequence formed by concatenating sequences 1, 2, 3, 4. The result is $(1, 2, 3, 4)$, and there is no number that appears more than twice, so the output is $-1$. The fourth query asks for the mode of the sequence formed by concatenating sequences 1, 2, 3, 4. The result is $(1, 2, 2, 4, 4, 4, 4)$, and the mode is 4.

Examples

Input 3

See major/major3.in and major/major3.ans in the contestant directory. This example satisfies the constraints for test cases 1 ~ 3.

Input 4

See major/major4.in and major/major4.ans in the contestant directory. This example satisfies the constraints for test cases 11 ~ 12.

Constraints

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

Special Property A: Guaranteed $n = 1$ and no operation 4. Special Property B: Guaranteed that at any time, any sequence only contains the numbers 1 and 2. Special Property C: Guaranteed no operation 2.