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,
There are
: 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
In the next
Each of the next
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
.
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
.
The fourth query is the mode of the sequence obtained after concatenating sequences
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