import sys


class MaxPairingHeap:
    # __slots__ drastically reduces memory overhead per object
    __slots__ = ['value', 'child', 'sibling']

    def __init__(self, value):
        self.value = value
        self.child = None
        self.sibling = None

    @staticmethod
    def merge(h1, h2):
        if h1 is None: return h2
        if h2 is None: return h1

        if h1.value >= h2.value:
            # h2 becomes the leftmost child of h1
            h2.sibling = h1.child
            h1.child = h2
            return h1
        else:
            # h1 becomes the leftmost child of h2
            h1.sibling = h2.child
            h2.child = h1
            return h2


def combine_children(first_child):
    if not first_child:
        return None

    # Pass 1: Merge pairs from left to right
    pairs = []
    curr = first_child
    while curr:
        h1 = curr
        h2 = curr.sibling
        if h2:
            next_curr = h2.sibling
            # Detach siblings before merging to avoid circularity/logic errors
            h1.sibling = None
            h2.sibling = None
            pairs.append(MaxPairingHeap.merge(h1, h2))
            curr = next_curr
        else:
            h1.sibling = None
            pairs.append(h1)
            curr = None

    # Pass 2: Merge from right to left
    if not pairs:
        return None

    new_root = pairs[-1]
    for i in range(len(pairs) - 2, -1, -1):
        new_root = MaxPairingHeap.merge(new_root, pairs[i])
    return new_root


class MergeHeapProblem:
    def __init__(self, file_prefix="mergeheap"):
        self.in_file_path = f"{file_prefix}.in"
        self.out_file_path = f"{file_prefix}.out"
        self.heaps = []

    def solve(self):
        try:
            with open(self.in_file_path, 'r') as f_in, open(self.out_file_path, 'w') as f_out:
                # Use a generator to read words for memory efficiency
                def get_input():
                    for line in f_in:
                        for word in line.split():
                            yield word

                tokens = get_input()

                try:
                    num_heaps = int(next(tokens))
                    num_operations = int(next(tokens))
                except StopIteration:
                    return

                # Pre-allocate list to avoid repeated resizing
                self.heaps = [None] * num_heaps

                for _ in range(num_operations):
                    op = next(tokens)

                    if op == '1':
                        m = int(next(tokens)) - 1
                        x = int(next(tokens))
                        new_node = MaxPairingHeap(x)
                        self.heaps[m] = MaxPairingHeap.merge(self.heaps[m], new_node)

                    elif op == '2':
                        m = int(next(tokens)) - 1
                        root = self.heaps[m]
                        if root is not None:
                            # Direct write to file to save RAM
                            f_out.write(f"{root.value}\n")
                            self.heaps[m] = combine_children(root.child)

                    elif op == '3':
                        m1 = int(next(tokens)) - 1
                        m2 = int(next(tokens)) - 1
                        if m1 != m2:
                            self.heaps[m1] = MaxPairingHeap.merge(self.heaps[m1], self.heaps[m2])
                            self.heaps[m2] = None
        except FileNotFoundError:
            pass


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


if __name__ == "__main__":
    main()