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.

Input Specification

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}~.

Output Specification

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

Samples

Sample inputs and outputs can be found here.

Sample Input 1

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

Sample Output 1

1
3
-1
3
-1

Explanation for Sample 1

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

Sample 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

Sample Output 2

-1
2
2
4

Explanation of Sample 2

The first query asks for the mode obtained after concatenating sequences ~1, 2, 3, 4~. The result of concatenation is ~(1, 2, 3, 4)~, and there is no number with more than two occurrences, so the output is -1. The fourth query is the mode of the sequence obtained after concatenating sequences ~1, 2, 3, 4~. The result of the concatenation is ~(1, 2, 2, 4, 4, 4, 4)~, which has a mode of ~4~.

Sample 3

See major3.in and major3.ans in the attachment package. This example satisfies the constraints of test cases 1∼3.

Sample 4

See major4.in and major4.ans in the attachment package. This example satisfies the constraints of 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}~.

Test Case	~n, q, C_m, C_l \le~	Additional Constraints
1~3	~300~	Property C
4~7	~4000~	Property C
8	~10^5~	Property A, B
9		Property A
10		Property B
11, 12		Property C
13		None
14	~5 \times 10^5~	Property A, B, C
15		Property A
16		Property B
17, 18		Property C
19, 20		None

Special properties:

• Property A: ~n = 1~, no operations of type 4.
• Property B: At any time, the sequences contain only ~1~s and ~2~s.
• Property C: No operations of type 2.