Sequence Mode Query

For a sequence, we define its mode as the number that appears strictly more than half of the sequence's length. Note that this definition is different from the standard definition and should be used as given.

Initially, there are \(n\) sequences (which can be empty) with indices \(1,2,\dots,n\). There will be \(q\) operations to be performed on these sequences. The operations can be of the following four 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: Remove the last number from sequence \(x\). It is guaranteed that sequence \(x\) exists and is non-empty.
• 3 m x1 x2 \(\ldots\) xm: Concatenate the sequences with indices \(x_1, x_2, \dots, x_m\) in order, forming a new sequence. Then, output the mode of the concatenated sequence according to the above definition. If no number occurs strictly more than half the times, output -1. Note that some indices may be repeated and the concatenation for the query does not affect future operations.
• 4 x1 x2 x3: Create a new sequence with index \(x_3\) which is the concatenation of sequence \(x_1\) followed by sequence \(x_2\), and then delete sequences \(x_1\) and \(x_2\). After this operation, sequence \(x_3\) exists, while \(x_1\) and \(x_2\) are considered non-existent and will not be used again.

Note: For any operation, it is guaranteed that the referenced sequences exist and satisfy the input constraints.

inputFormat

The first line contains two integers \(n\) and \(q\), representing the initial number of sequences and the number of operations, respectively.

Each of the following \(q\) lines contains an operation in one of the four types described above.

outputFormat

For each operation of type 3, output a single line containing the mode of the concatenated sequence. If there is no number that occurs strictly more than half of the time in the concatenated sequence, output -1.

sample

3 5
1 1 5
1 1 5
3 1 1
2 1
3 1 1

5
5