class MaxPairingHeap:
    def __init__(self, value):
        self.value = value
        self.children = []

    def merge(self, other):
        if not other:
            return self

        if self.value >= other.value:
            self.children.append(other)
            return self
        else:
            other.children.append(self)
            return other

    def add(self, value):
        new_heap = MaxPairingHeap(value)
        return self.merge(new_heap)

    def pop(self):
        if not self.children:
            return None

        # Pass 1: Merge pairs from left to right
        pairs = []
        for i in range(0, len(self.children), 2):
            if i + 1 < len(self.children):
                pairs.append(self.children[i].merge(self.children[i + 1]))
            else:
                pairs.append(self.children[i])

        # Pass 2: Merge pairs from right to left
        # This is CRITICAL for the O(log n) complexity bound
        new_root = pairs[-1]
        for i in range(len(pairs) - 2, -1, -1):
            new_root = new_root.merge(pairs[i])
        return new_root

    def get_max(self):
        return self.value


class MergeHeapProblem:
    def __init__(self, file_prefix="tests/mergeheap"):
        self.in_file_path = f"{file_prefix}.in"
        self.out_file_path = f"{file_prefix}.out"
        self.ground_truth_file_path = f"{file_prefix}.ok"

        self.output_str = ""

        self.heaps = []

    def read_input(self):
        with open(self.in_file_path, 'r') as f:
            # First line contains 2 integers
            # num_heaps and num_operations
            first_line = f.readline().strip()
            num_heaps, num_operations = map(int, first_line.split())

            # Then each line contains an operation
            # op 1 - add into heap m the element x
            # op 2 - print max of heap m and then pop max from heap m
            # op 3 - merge heap m1 and m2 (m2 into m1, m2 becomes empty)

            for _ in range(num_operations):
                line = f.readline().strip()
                parts = line.split()
                op = int(parts[0])

                if op == 1:
                    m = int(parts[1]) - 1
                    x = int(parts[2])
                    # Ensure index exists
                    while len(self.heaps) <= m:
                        self.heaps.append(None)

                    new_node = MaxPairingHeap(x)
                    if self.heaps[m] is None:
                        self.heaps[m] = new_node
                    else:
                        # Don't call .add(), just use the merge logic directly
                        self.heaps[m] = self.heaps[m].merge(new_node)

                elif op == 2:
                    m = int(parts[1]) - 1
                    if self.heaps[m] is not None:
                        self.output_str += f"{self.heaps[m].get_max()}\n"
                        self.heaps[m] = self.heaps[m].pop()

                elif op == 3:
                    m1 = int(parts[1]) - 1
                    m2 = int(parts[2]) - 1
                    if self.heaps[m1] is not None and self.heaps[m2] is not None:
                        self.heaps[m1] = self.heaps[m1].merge(self.heaps[m2])
                        self.heaps[m2] = None
                    elif self.heaps[m1] is None and self.heaps[m2] is not None:
                        self.heaps[m1] = self.heaps[m2]
                        self.heaps[m2] = None

    def write_output(self):
        with open(self.out_file_path, 'w') as f:
            f.write(self.output_str)

    def validate_output(self):
        with open(self.out_file_path, 'r') as f:
            output = f.read().strip()
        with open(self.ground_truth_file_path, 'r') as f:
            ground_truth = f.read().strip()

        assert output == ground_truth, f"Output does not match ground truth.\nOutput:\n{output}\nGround Truth:\n{ground_truth}"

    def solve(self):
        self.read_input()
        self.write_output()


def main():
    problem = MergeHeapProblem("mergeheap")
    problem.solve()
    # problem.validate_output()


if __name__ == "__main__":
    main()