A priority queue is a data structure which maintains a set $S$ of elements, each of with an associated value (key), and supports the following operations:

* $insert(S, k)$: insert an element $k$ into the set $S$
* $extractMax(S)$: remove and return the element of $S$ with the largest key



Write a program which performs the $insert(S, k)$ and $extractMax(S)$ operations to a priority queue $S$. The priority queue manages a set of integers, which are also keys for the priority.

Constraints

* The number of operations $\leq 2,000,000$
* $0 \leq k \leq 2,000,000,000$

Input

Multiple operations to the priority queue $S$ are given. Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.

The input ends with "end" operation.

Output

For each "extract" operation, print the element extracted from the priority queue $S$ in a line.

Example

Input

insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end


Output

8
10
11
2
import java.util.*;

public class Main {

	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {-1, 0, 1, 0};
	static long MOD = (long) (1e9 + 7);
	  
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		String s = in.next();
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
		
		while (!"end".equals(s)) {
			if ("insert".equals(s)) {
				int i = in.nextInt();
				q.add(i);
			} else {
				System.out.println(q.poll());
			}
			s = in.next();
		}
	}
	
	public static int maxSideLength(int[][] mat, int threshold) {
		if (mat == null || mat.length == 0 || mat[0].length == 0) {
			return 0;
		}
		
		int M = mat.length;
		int N = mat[0].length;
		
		// Precompute the sum
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				mat[i][j] = getAt(mat, i, j) + getAt(mat, i - 1, j) + getAt(mat, i, j - 1) - getAt(mat, i - 1, j - 1);
			}
		}
		
		int ans = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 1; i + k < M && j + k < N; k++) {
					int area = getAt(mat, i + k, j + k) - getAt(mat, i + k, j - 1) - getAt(mat, i - 1, j + k) + getAt(mat, i - 1, j - 1);
					if (area <= threshold) {
						ans = Math.max(ans, k + 1);
					}
				}
			}
		}
		
		return ans;
	}
	
	public static int getAt(int[][] mat, int i, int j) {
		if (i < 0 || j < 0) return 0;
		return mat[i][j];
	}
	
    public static List<Integer> findAnagrams(String s, String p) {
    	List<Integer> ans = new ArrayList<Integer>();
        
    	int[] pfreq = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pfreq[p.charAt(i) - 'a']++;
        }
        
        int[] sfreq = new int[26];
        for (int i = 0; i < p.length() && i < s.length(); i++) {
        	sfreq[s.charAt(i) - 'a']++;
        }
        
        // key is in the format character###,
        String pkey = "";
        String skey = "";
        
        for (int i = 0; i < 26; i++) {
        	pkey += String.format("%c%d,", i + 'a', pfreq[i]);
        	skey += String.format("%c%d,", i + 'a', sfreq[i]);
        }
        
        for (int i = p.length(); i < s.length(); i++) {
        	char removed = s.charAt(i - p.length());
        	char added = s.charAt(i);
        	
        	
        }
        
        return ans;
    }

	public static int count(String[] arr, Map<String, Map<Character, TreeSet<Integer>>> map, String s) {
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			if (subsequence(s, map.get(arr[i]))) {
				count++;
			}
		}
		return count;
	}
	
	public static boolean subsequence(String s, Map<Character, TreeSet<Integer>> map) {
		char f = s.charAt(0);
		char m = s.charAt(1);
		char e = s.charAt(2);
		if (!map.containsKey(f) || !map.containsKey(m) || !map.containsKey(e)) {
			return false;
		}
		
		Iterator<Integer> it = map.get(m).iterator();
		while (it.hasNext()) {
			int index = it.next();
			if (map.get(f).lower(index) != null && map.get(e).higher(index) != null) {
				return true;
			}
		}
		
		return false;
	}
	
	public static String str(int i, int j, int k) {
		return String.format("%c%c%c", c(i), c(j), c(k));
	}
	
	public static char c(int i) {
		if (i < 26) {
			return (char) ('A' + i);
		} else {
			i -= 26;
			return (char) ('a' + i);
		}
	}
	
	public static int sol(int N, int k) {
		if (N == 1 && k == 1) return 1;
		int parent = sol(N - 1, (k + 1) / 2);
		if (k % 2 == 0) {
			return (parent + 1) % 2;
		} else {
			return parent;
		}
	}
	
	public static double calculate(double base, double n) {
        return Math.pow(Math.E, Math.log(base)/n);
    }
	
	public static int partition(int[] nums, int low, int high) { // [1,2], 0, 1
		// Pick the first element as pivot
		// int pivot = nums[low]; // 1
		//
		// int left = low + 1; // 2
		// int right = high; // 1
		//
		//
		// while (left <= right) { // This equal to is important to move right
		// cursor left cursor correct position
		// if (nums[left] <= pivot) {
		// left++;
		// continue;
		// }
		// if (pivot <= nums[right]) {
		// right--;
		// continue;
		// }
		// int tmp = nums[left];
		// nums[left] = nums[right];
		// nums[right] = tmp;
		// }
		// int tmp = nums[low];
		// nums[low] = nums[right];
		// nums[right] = tmp;
		//
		// return right;

		// Pick the last element as pivot
		int pivot = nums[high];

		int left = low;
		int right = high - 1;

		while (left <= right) {
			if (nums[left] <= pivot) {
				
				left++;
				continue;
			}
			if (pivot <= nums[right]) {
				right--;
				continue;
			}
			int tmp = nums[left];
			nums[left] = nums[right];
			nums[right] = tmp;
		}
		int tmp = nums[high];
		nums[high] = nums[left];
		nums[left] = tmp;

		return left;
	}

	// Pivot is the first element
	public static int partitionFront(int[] nums, int low, int high) {
		int pivot = nums[low];

		int left = low + 1;

		while (left <= high) {
			// Increment left until it reaches the element greater than pivot
			while (left <= high && nums[left] <= pivot)
				left++;
			while (left <= high && nums[high] >= pivot)
				high--;

			if (left < high) {
				int tmp = nums[left];
				nums[left] = nums[high];
				nums[high] = tmp;
			}
		}
		int tmp = nums[low];
		nums[low] = nums[high];
		nums[high] = tmp;

		return high;
	}

	// Pivot is the last element
	public static int partitionBack(int[] nums, int low, int high) {
		int pivot = nums[high];

		int right = high - 1;

		while (low <= right) {
			// Increment low until it is greater than pivot
			while (low <= right && nums[low] <= pivot)
				low++;
			// Decrement right until it is less than pivot
			while (low <= right && nums[right] >= pivot)
				right--;

			if (low < right) {
				int tmp = nums[low];
				nums[low] = nums[right];
				nums[right] = tmp;
			}
		}

		int tmp = nums[low];
		nums[low] = nums[high];
		nums[high] = tmp;

		return low;
	}

	public static void out(Object o) {
		System.out.println(o);
	}

	public static void print(Object o) {
		System.out.print(o);
	}

	public static void printNumArray(int[] nums) {
		System.out.printf("[");
		for (int i = 0; i < nums.length; i++) {
			System.out.printf("%d%s", nums[i], i != nums.length - 1 ? ", " : "");
		}
		System.out.println("]");
	}

	public static void printNumArray(long[] nums) {
		System.out.printf("[");
		for (int i = 0; i < nums.length; i++) {
			System.out.printf("%d%s", nums[i], i != nums.length - 1 ? ", " : "");
		}
		System.out.println("]");
	}

	public static void printDoubleArray(double[] nums) {
		System.out.printf("[");
		for (int i = 0; i < nums.length; i++) {
			System.out.printf("%f%s", nums[i], i != nums.length - 1 ? ", " : "");
		}
		System.out.println("]");
	}

	public static void printDoubleList(List<List<Integer>> nums) {
		for (int i = 0; i < nums.size(); i++) {
			printNumList(nums.get(i));
		}
	}

	public static void printNumList(List<Integer> nums) {
		System.out.printf("[");
		for (int i = 0; i < nums.size(); i++) {
			System.out.printf("%d%s", nums.get(i), i != nums.size() - 1 ? ", " : "");
		}
		System.out.println("]");
	}

	public static void printStringList(List<String> list) {
		System.out.printf("[");
		for (int i = 0; i < list.size(); i++) {
			System.out.printf("%s%s", list.get(i), i != list.size() - 1 ? ", " : "");
		}
		System.out.println("]");
	}

	public static void printStringArray(String[] arr) {
		print("[");
		for (int i = 0; i < arr.length; i++) {
			print(String.format("%s%s", arr[i], i != arr.length - 1 ? ", " : ""));
		}
		out("]");
	}

	public static void printStringListOfStringList(List<List<String>> list) {
		for (int i = 0; i < list.size(); i++) {
			printStringList(list.get(i));
		}
	}

	public static void printNumListOfNumList(List<List<Integer>> num) {
		for (int i = 0; i < num.size(); i++) {
			printNumList(num.get(i));
		}
	}
	
	public static void printNumListOfNumArray(List<int[]> list) {
		for (int i = 0; i < list.size(); i++) {
			printNumArray(list.get(i));
		}
	}

	public static void printNum2DArray(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.printf("%2d ", map[i][j]);
			}
			System.out.println();
		}
	}

	public static void printNum2DArray(long[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.printf("%2d ", map[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void printCharArray(char[] arr) {
		print("[");
		for (int i = 0; i < arr.length; i++) {
			System.out.printf("%c%s", arr[i], i == arr.length - 1 ? "" : ", ");
		}
		out("]");
	}

	public static void printChar2DArray(char[][] map) {
		for (char[] arr : map) {
			for (char c : arr) {
				print(String.format("%c ", c));
			}
			out("");
		}
	}

	public static void printBoolean2DArray(boolean[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				print(map[i][j] ? "T " : "F ");
			}
			out("");
		}
	}

	public static void printListNode(ListNode node) {
		boolean first = true;
		while (node != null) {
			if (!first) {
				print("->");
			}
			print(node.val);
			node = node.next;
			first = false;
		}
	}

	public static void printStringSet(Set<String> set) {
		for (String s : set) {
			out(s);
		}
	}

	/**
	 * Receives an integer and print in numBits from the right
	 * 
	 * @param n
	 * @param numBits
	 */
	public static void printBinary(int n, int numBitsFromRight) {
		String s = "";
		for (int i = numBitsFromRight - 1; i >= 0; i--) {
			s += (n & (1 << i)) > 0 ? "1" : "0";
		}
		out(s);
	}

	// Taken from
	// https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/
	public static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
	
	public static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	public static long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}
	
	public static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

class CustomClass {
	String to;
	double dist;

	public CustomClass(String to, double dist) {
		this.to = to;
		this.dist = dist;
	}
}

class TreeDrawer {
	public static String treeNodeToString(TreeNode root) {
		if (root == null) {
			return "[]";
		}

		String output = "";
		Queue<TreeNode> nodeQueue = new LinkedList<>();
		nodeQueue.add(root);
		while (!nodeQueue.isEmpty()) {
			TreeNode node = nodeQueue.remove();

			if (node == null) {
				output += "null, ";
				continue;
			}

			output += String.valueOf(node.val) + ", ";
			nodeQueue.add(node.left);
			nodeQueue.add(node.right);
		}
		return "[" + output.substring(0, output.length() - 2) + "]";
	}

	public static TreeNode stringToTreeNode(String input) {
		input = input.trim();
		input = input.substring(1, input.length() - 1);
		if (input.length() == 0) {
			return null;
		}

		String[] parts = input.split(",");
		String item = parts[0];
		TreeNode root = new TreeNode(Integer.parseInt(item));
		Queue<TreeNode> nodeQueue = new LinkedList<>();
		nodeQueue.add(root);

		int index = 1;
		while (!nodeQueue.isEmpty()) {
			TreeNode node = nodeQueue.remove();

			if (index == parts.length) {
				break;
			}

			item = parts[index++];
			item = item.trim();
			if (!item.equals("null")) {
				int leftNumber = Integer.parseInt(item);
				node.left = new TreeNode(leftNumber);
				nodeQueue.add(node.left);
			}

			if (index == parts.length) {
				break;
			}

			item = parts[index++];
			item = item.trim();
			if (!item.equals("null")) {
				int rightNumber = Integer.parseInt(item);
				node.right = new TreeNode(rightNumber);
				nodeQueue.add(node.right);
			}
		}
		return root;
	}

	public static void prettyPrintTree(TreeNode node, String prefix, boolean isLeft) {
		if (node == null) {
			System.out.println("Empty tree");
			return;
		}

		if (node.right != null) {
			prettyPrintTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
		}

		System.out.println(prefix + (isLeft ? "└── " : "┌── ") + node.val);

		if (node.left != null) {
			prettyPrintTree(node.left, prefix + (isLeft ? "    " : "│   "), true);
		}
	}

	public static void draw(TreeNode node) {
		prettyPrintTree(node, "", true);
	}
}

class Interval {
	int start;
	int end;

	Interval() {
		start = 0;
		end = 0;
	}

	Interval(int s, int e) {
		start = s;
		end = e;
	}
}

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}


