def siftup(ind):
    global heap
    while ind > 1 and heap[ind] > heap[ind // 2]:
        heap[ind], heap[ind // 2] = heap[ind // 2], heap[ind]
        ind //= 2
    return ind


def siftdown(ind):
    global heap
    while 2 * ind < len(heap):
        best = 2 * ind
        if  2 * ind + 1 < len(heap) and heap[best + 1] > heap[best]:
            best += 1
        if heap[ind] >= heap[best]:
            return
        heap[ind], heap[best] = heap[best], heap[ind]
        ind = best


def add(el):
    global heap
    heap.append(el)
    siftup(len(heap) - 1)


def remove(ind):
    global heap
    heap[ind], heap[-1] = heap[-1], heap[ind]
    elem = heap.pop()
    if ind == len(heap):
        return elem
    ind = siftup(ind)
    siftdown(ind)
    return elem

fin = open('priority-queue.in')
commands = [s.rstrip().split() for s in fin.readlines()]
fin.close()
heap = [0]
dic = {}
fout = open('priority-queue.out', 'w')
for s in commands:
    if s[0] != 'POP':
        s[2] = int(s[2])#priority
for s in commands:
    if s[0] == 'ADD':
        add(s[2])
        dic[s[1]] = s[2]
    if s[0] == 'POP':
        ans = remove(1)
        for i in dic.keys():
            if dic[i] == ans:
                print(i, dic[i], file = fout)
                dic[i] = 'nothing'
                break
    if s[0] == 'CHANGE':
        elem = dic[s[1]]
        dic[s[1]] = s[2]
        i = 1
        while heap[i] != elem:
            i += 1
        heap[i] = s[2]
        ind = siftup(i)
        siftup(ind)
fout.close()