#NOI20221A. 「NOI2022」众数 (Majority element)

「NOI2022」众数 (Majority element)

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 nn positive integer sequences of varying length, labeled by 1n1 \sim n. The initial sequence may be empty. These nn sequences exist while sequences labelled by other numbers are deemed non-existent.

There are qq operations of following types:

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

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

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

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

Input Format

Read from file major.in.

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

For the following nn lines, the iith line corresponds to sequence ii. Each line begins with a non-negative integer lil_i indicating the number count of the initial iith sequence. Following are lil_i nonnegative numbers ai,ja_{i,j} representing the numbers in the sequence in order. Suppose Cl= liC_l = \sum\ l_i is the sum of length of the inputted sequences, then it is guaranteed that Cl5×105C_l \leq 5 \times 10^5, ai,jn+qa_{i,j} \leq n+q.

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

Suppose Cm=mC_m = \sum m is the sum of number of sequences to be concatenated in all type 33 operations, then it is guaranteed that Cm5×105C_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 131 \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 111211 \sim 12.

Constraints and Hint

For all the tests, 1n,q,Cm,Cl5×1051 \leq n,q,C_m,C_l \leq 5 \times 10^5.

n,qn,q Cm,ClC_m,C_l Test Number Special Case A Special Case B Special Case C
300\leq 300 131 \sim 3 No Yes
4000\leq 4000 474 \sim 7
105\leq 10^5 88 Yes Yes
99 No No
1010 No Yes
111211 \sim 12 No Yes
1313 No
5×105\leq 5 \times 10^5 1414 Yes Yes
1515 No No
1616 No Yes
171817 \sim 18 No Yes
192019 \sim 20 No

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

Special case B: It is guaranteed that at any time and in any sequence there are only numbers 11 and 22.

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