#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int c;
	while(scanf("%d\n", &c) > 0){
		int l;
		bool gs = 1;
		scanf("%d\n", &l);
		vector<int> printList;
		for(int i = 0; i < l; i++){
			int temp;
			scanf("%d\n", &temp);
			printList.push_back(temp);
		}
		sort(printList.begin(), printList.end());
		map<int, int> prc;
		int mode = 1;
		int cs = 1;

		int maxCs = printList[l-1];
		int offset = 0;
		while(1){
			char cmd;
			scanf("%c\n", &cmd);
			if(cmd == 'e') break;
			else if(cmd == 'a'){
				int cost;
				scanf("%d\n", &cost);
				if(!gs) continue;
				map<int, int>::iterator it = prc.find(cost);
				if(it == prc.end()){
					prc.insert(pair<int, int>(cost, 1));
				}
				else{
					it->second ++;
				}
			}
			else if(cmd == 'p'){
				scanf("%d\n", &mode);
			}
			else{
				if(!gs) continue;
				if(prc.empty()) {
					printf("-1\n");
					continue;
				}
				map<int, int>::iterator it;
				if(mode == 1) it = prc.begin();
				else{
					it = prc.end();
					it--;
				}
				int tar = it->first;
				it->second --;
				if(it->second == 0){
					prc.erase(it);
				}

				while(offset < l && printList[offset] < cs){
					offset++;
				}
				if(offset < l && printList[offset] == cs){
					offset++;
					printf("%d\n", tar);
				}

				cs++;
				if(cs > maxCs) gs = 0;
			}
		}
		printf("\n");
	}
	return 0;
}