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, positive integer sequences of different lengths are given, numbered from to , and the sequences can be empty. These sequences are considered to exist, and the sequences corresponding to other numbers are considered to be non-existent.
There are operations, and operations are of the following types:
- : Insert the number at the end of sequence . It is guaranteed that sequence exists and .
- : Delete the number at the end of sequence . It is guaranteed that sequence exists, is not empty, and .
- : Concatenate sequences to get a new sequence and return its mode. Return
-1
if the mode does not exist. The data guarantees that for any the sequence numbered still exists, , and the concatenated sequence is non-empty. There is no guarantee that are distinct. The concatenation done here won't affect future operations. - : Create a new sequence numbered , which is the concatenation of sequence and sequence . Then, delete the sequences numbered and . After this operation, sequence is considered to exist, and the sequences and are considered to be non-existent and will not be used again in subsequent operations. It is guaranteed that , , the sequences and existed before the operation, and no operation used the sequence numbered before the operation.
Input Specification
The first line of input contains two positive integers and , which represent the number of initial sequences and the number of operations, respectively. It is guaranteed that .
In the next lines, the -th line represents the sequence numbered . The first non-negative integer of each line represents the length of the -th sequence, followed by non-negative integers representing the elements of the sequence in order. Let represent the sum of the input sequence lengths, then it is guaranteed that and .
Each of the next lines represent an operation in the format described above, consisting of several integers. Let represent the sum of all sequences that need to be concatenated in operation 3, then it is guaranteed that .
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 . Since the sequence contains two s, more than half the length of the sequence, the mode is .
The second query queries the mode of sequence . Since the sequence contains only s, the mode is .
The third query asks for the mode of sequence . At this time, sequence is , and there is no number occuring more than 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 . The result of concatenation is , 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 . The result of the concatenation is , which has a mode of .
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 .
Test Case | Additional Constraints | |
---|---|---|
1~3 | Property C | |
4~7 | Property C | |
8 | Property A, B | |
9 | Property A | |
10 | Property B | |
11, 12 | Property C | |
13 | None | |
14 | Property A, B, C | |
15 | Property A | |
16 | Property B | |
17, 18 | Property C | |
19, 20 | None |
Special properties:
- Property A: , no operations of type 4.
- Property B: At any time, the sequences contain only s and s.
- Property C: No operations of type 2.
Comments