class HeapNode:
    def __init__(self, val):
        self.val = val
        self.children = []


class PairingHeap:
    def __init__(self):
        self.root = None
        self.nodes = []

    def insert(self, key):
        node = HeapNode(key)
        self.nodes.append(node)
        self.root = self._merge(self.root, node)

    def _merge(self, root1, root2):
        if root1 is None:
            return root2
        elif root2 is None:
            return root1
        elif root1.val < root2.val:
            root1.children.append(root2)
            return root1
        else:
            root2.children.append(root1)
            return root2

    def print_nodes(self):
        if len(self.nodes):
            for node in self.nodes:
                print(node.val, sep=" ")
        else:
            print("No nodes!")
        print("\n")
        return

    def max_node(self):
        return max(node.val for node in self.nodes)

    def delete_max(self):
        if len(self.nodes) == 0:
            raise ValueError("Heap is empty!")
        else:
            max_node = max(self.nodes, key=lambda node: node.val)
            self.nodes.remove(max_node)
            return max_node.val


def merge_and_empty(first_heap, second_heap):
    for node in second_heap.nodes:
        first_heap.insert(node.val)
    second_heap.nodes = []

#functia care rezolva problema mergeheap de pe infoarena
def read_file(file):
    with open(file, "r") as f1:
        with open("mergeheap.out", "w") as f2:
            x = list(f1.readline().split())
            N = int(x[0])  # nr multimi
            Q = int(x[1])  # nr operatii
            heaps = []  # aici tinem heap-urile
            # am creat N heap-uri
            for i in range(N):
                heap = PairingHeap()
                heaps.append(heap)
            i = 0
            while i < Q:
                x = list(f1.readline().split())
                operation_type = x[0]
                heap_nr = int(x[1]) - 1
                if operation_type == "1":
                    number_to_be_added = x[2]
                    heaps[heap_nr].insert(number_to_be_added)

                elif operation_type == "2":
                    maxnode = heaps[heap_nr].max_node()
                    f2.write(maxnode)
                    f2.write("\n")
                    if maxnode is not None:
                        heaps[heap_nr].delete_max()



                else:

                    heap_nr2 = int(x[2]) - 1
                    merge_and_empty(heaps[heap_nr], heaps[heap_nr2])

                i += 1


if __name__ == '__main__':
    read_file("mergeheap.in")