class BinomialHeapNode:
    def __init__(self, value):
        self.value = value
        self.rank = 0
        self.children = []

    def __lt__(self, other):
        return self.value < other.value


class BinomialHeap:
    def __init__(self):
        self.trees = []

    def insert(self, value):
        node = BinomialHeapNode(value)
        heap = BinomialHeap()
        heap.trees.append(node)
        self.merge(heap)

    def merge(self, other):
        self.trees.extend(other.trees)
        self.trees.sort(key=lambda x: x.rank)
        self._combine_trees()

    def _combine_trees(self):
        i = 0
        while i < len(self.trees) - 1:
            current_tree = self.trees[i]
            next_tree = self.trees[i + 1]
            if current_tree.rank == next_tree.rank:
                if current_tree < next_tree:
                    current_tree.children.append(next_tree)
                else:
                    next_tree.children.append(current_tree)
                del self.trees[i + 1]
            i += 1

    def get_max(self):
        if len(self.trees) == 0:
            return None
        max_node = self.trees[0]
        for node in self.trees[1:]:
            if node < max_node:
                break
            max_node = node
        return max_node.value

    def extract_max(self):
        if len(self.trees) == 0:
            return None
        max_node_index = 0
        for i in range(1, len(self.trees)):
            if self.trees[i] > self.trees[max_node_index]:
                max_node_index = i
        max_node = self.trees[max_node_index]
        del self.trees[max_node_index]
        new_heap = BinomialHeap()
        new_heap.trees.extend(reversed(max_node.children))
        self.merge(new_heap)
        return max_node.value


with open("mergeheap.in", "r") as input_file, open("mergeheap.out", "w") as output_file:
    N, Q = map(int, input_file.readline().split())
    heaps = [BinomialHeap() for _ in range(N)]

    for _ in range(Q):
        operation = list(map(int, input_file.readline().split()))
        if operation[0] == 1:
            x = operation[2]
            heap_idx = operation[1] - 1
            if heap_idx < N:
                heaps[heap_idx].insert(x)
        elif operation[0] == 2:
            heap_idx = operation[1] - 1
            if heap_idx < N:
                max_element = heaps[heap_idx].extract_max()
                if max_element is not None:
                    output_file.write(str(max_element) + "\n")
        elif operation[0] == 3:
            heap_idx_a = operation[1] - 1
            heap_idx_b = operation[2] - 1
            if heap_idx_a < N and heap_idx_b < N:
                heaps[heap_idx_a].merge(heaps[heap_idx_b])