import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    static int[] Heap; 
    static int closest_empty_node_idx;

    public static void push(int node) {
        Heap[closest_empty_node_idx] = node;
        int now_idx = closest_empty_node_idx;
        
        
        closest_empty_node_idx ++;
        while (now_idx != 0) {
            int parent_idx = (now_idx-1) / 2;
            if (Heap[parent_idx] > Heap[now_idx]) {
                int temp = Heap[parent_idx];
                Heap[parent_idx] = Heap[now_idx];
                Heap[now_idx] = temp;
                now_idx = parent_idx;
            } else {
                break;
            }
        }
    }
    
    public static int pop() {
        int pop_value = Heap[0];
        Heap[0] = Heap[closest_empty_node_idx-1];
        Heap[closest_empty_node_idx-1] = 0;
        closest_empty_node_idx--;
        int limit = closest_empty_node_idx;
        
        int this_idx = 0;
        while (this_idx < limit) {
            int child_left = this_idx*2 + 1;
            int child_right = this_idx*2 + 2;
            
            int smallest_idx = this_idx;

            if (child_left < limit && Heap[this_idx] > Heap[child_left]) {
                smallest_idx = child_left;
            }

            if (child_right < limit && Heap[child_right] < Heap[smallest_idx]) {
                smallest_idx = child_right;
            }
            
            if (smallest_idx == this_idx) {
                break;
            } else {             
                int temp = Heap[this_idx];
                Heap[this_idx] = Heap[smallest_idx];
                Heap[smallest_idx] = temp;
                this_idx = smallest_idx;
            }   
        }
        return pop_value;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        Heap = new int[20005];
        
        for (int i=0; i<N; i++) {
            Heap[i] = Integer.parseInt(st.nextToken());
        }
        
        closest_empty_node_idx = N;
        StringBuilder sb = new StringBuilder();
        
        for (int q = 0; q < Q; q++) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            
            if (s.equals("push")) {
                int next_node = Integer.parseInt(st.nextToken());
                push(next_node);
            }
            
            if (s.equals("pop")) {
                sb.append(pop()).append("\n");
            }    
        }
        for (int i=0; i < closest_empty_node_idx; i++) {
            if (i== closest_empty_node_idx-1) {
                sb.append(Heap[i]);
            } else {
                sb.append(Heap[i]).append(" ");
            }
        }
        System.out.println(sb);
        
                

        
        
        
    }
}