SM

from typing import List, Any


def sift_up(heap: List[Any], pos: int) -> None:
    par = (pos - 1) // 2
    while par >= 0:
        if heap[par] < heap[pos]:
            heap[par], heap[pos] = heap[pos], heap[par]
        else:
            return None
        pos, par = par, (par - 1) // 2


def sift_down(heap: List[Any], length: int) -> None:
    pos = 0
    while pos * 2 + 1 < length:
        if pos * 2 + 2 < length and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
            child = pos * 2 + 2
        else:
            child = pos * 2 + 1
        if heap[child] > heap[pos]:
            heap[child], heap[pos] = heap[pos], heap[child]
        pos = child


def heap_sort(arr: List[Any]) -> List[Any]:
    heap = []
    for i in range(len(arr)):
        heap.append(arr[i])
        sift_up(heap, i - 1)
    heap_len = len(heap)
    while heap_len > 1:
        if heap[heap_len - 1] < heap[0]:
            heap[heap_len - 1], heap[0] = heap[0], heap[heap_len - 1]
        heap_len -= 1
        sift_down(heap, heap_len)
    return heap


A = list(map(int, input().split()))
print(' '.join(map(str, heap_sort(A))))


SN

from typing import List, Any


def sift_up(heap: List[Any], pos: int) -> int:
    par = (pos - 1) // 2
    while par >= 0:
        if heap[par] < heap[pos]:
            heap[par], heap[pos] = heap[pos], heap[par]
        else:
            return pos
        pos, par = par, (par - 1) // 2
    return pos


def sift_down(heap: List[Any], length: int) -> None:
    pos = 0
    while pos * 2 + 1 < length:
        if pos * 2 + 2 < length and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
            child = pos * 2 + 2
        else:
            child = pos * 2 + 1
        if heap[child] > heap[pos]:
            heap[child], heap[pos] = heap[pos], heap[child]
        pos = child


n = int(input())
A = list(map(int, input().split()))
for j in range(int(input())):
    i, x = map(int, input().split())
    A[i] += x
    print(sift_up(A, i))
print(' '.join(map(str, A)))


SO

from typing import List, Any


def sift_up(heap: List[Any], pos: int) -> int:
    par = (pos - 1) // 2
    while par >= 0:
        if heap[par] < heap[pos]:
            heap[par], heap[pos] = heap[pos], heap[par]
        else:
            return pos
        pos, par = par, (par - 1) // 2
    return pos


def sift_down(heap: List[Any], pos: int) -> int:
    ans = pos
    while pos * 2 + 1 < len(heap):
        if pos * 2 + 2 < len(heap) and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
            child = pos * 2 + 2
        else:
            child = pos * 2 + 1
        if heap[child] > heap[pos]:
            heap[child], heap[pos] = heap[pos], heap[child]
            ans = child
        pos = child
    return ans


n = int(input())
A = list(map(int, input().split()))
for j in range(int(input())):
    i, x = map(int, input().split())
    A[i] -= x
    print(sift_down(A, i))
print(' '.join(map(str, A)))

SP


from typing import List, Any


def sift_up(heap: List[Any], pos: int) -> int:
    par = (pos - 1) // 2
    while par >= 0:
        if heap[par] < heap[pos]:
            heap[par], heap[pos] = heap[pos], heap[par]
        else:
            return pos
        pos, par = par, (par - 1) // 2
    return pos


def sift_down(heap: List[Any]) -> int:
    ans = pos = 0
    while pos * 2 + 1 < len(heap):
        if pos * 2 + 2 < len(heap) and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
            child = pos * 2 + 2
        else:
            child = pos * 2 + 1
        if heap[child] > heap[pos]:
            heap[child], heap[pos] = heap[pos], heap[child]
            ans = child
        pos = child
    return ans


def insert(heap: List[int], x: int) -> int:
    if len(heap) == n:
        return -1
    heap.append(x)
    return sift_up(heap, len(heap) - 1)


def extract(heap: List[int]) -> List[Any]:
    if len(heap):
        heap[-1], heap[0] = heap[0], heap[-1]
        ans = heap.pop()
        return [sift_down(heap), ans]
    return [-1]


n, m = map(int, input().split())
queue = []  # type: List[int]
for j in range(m):
    r = list(map(int, input().split()))
    if r[0] == 1:
        print(*extract(queue))
    else:
        print(insert(queue, r[1]))
print(' '.join(map(str, queue)))