// G5BADS coursework by Ho Duc Thang (dth03u)


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

public class Scheduler {
	int ktree=1;//higher ktree,faster insert(),slower next()
	int lim=100001;//smaller lim,faster next() for very big test,length >> lim.
				//If length just a bit > lim then next() will be slower but not too much
	final static int oo = Integer.MAX_VALUE;
	final static int INCREASE = 100000;
	int LIMIT = 1000000;
	int size=0;
	int[] knary = new int[LIMIT];
	String[] des =  new String[LIMIT];
	int start=0;
	int time=0;
	boolean sorted=false;

	public Scheduler() {}

	public void insert_sort(int start,int end){
		for (int i=start+1;i<=end;++i){
			for (int j=i;j>start;--j){
				if (knary[j]<knary[j-1]){
					exchange(j,j-1);
				}//end of if
			}//end of for
		}//end of for

	}

	public void QuickSort(int l, int r) {//sort from index l to index r inclusive
		if (r-l<1)return;
		if (r-1==l){
			if (knary[r]<knary[l]) exchange(l,r);
			return;
		};
		int i = (r+l)/2;;
		int j=r-1;

		// Tri-Median Methode
		// This algorithm offers n*log(n) performance on many data sets
		//that cause other quicksorts to degrade to quadratic performance
		if (knary[l]>knary[i]) exchange(l,i);
		if (knary[l]>knary[r]) exchange(l,r);
		if (knary[i]>knary[r]) exchange(i,r);

		exchange(i,j);
		i = l;
		int v = knary[j];
		for(;;)
		{
			while(knary[++i]<v);
			while(knary[--j]>v);
			if (j<i) break;
			exchange (i,j);
		}
		exchange(i,r-1);

		if (j-l+1>10) {
			QuickSort(l,j);
		} else {
			insert_sort(l,j);
		}//run insertion sort for small test length <10

		if (r-i>10){
			QuickSort(i+1,r);
		} else {
			insert_sort(i+1,r);
		}//run insertion sort for small test length <10

	};


	public void expand() {
		LIMIT += INCREASE;
		int[] a = new int[LIMIT];
		System.arraycopy(knary,start,a,0,size);
		knary = a;

		String[] b = new String[LIMIT];
		System.arraycopy(des,start,b,0,size);
		des = b;
		start=0;
	}

	public void exchange(int i, int j) {
		int tmp = knary[i];
		knary[i] = knary[j];
		knary[j] = tmp;

		String temp = des[i];
		des[i] = des[j];
		des[j] = temp;
	}

	public boolean empty() {
		return (size==0);
	}

	public void goUp(int p) {
		//if p is not in correct position then sorted=false;
		if (p>0 && knary[start+p]<knary[start+((p-1)>>ktree)])
			sorted=false;
		while (p>0 && knary[start+p]<knary[start+((p-1)>>ktree)]) {
			exchange(start+p,start+ ((p-1)>>ktree));
			p=(p-1)>>ktree;
		};//end of finding correct position for p
	}

	public void goDown(int p) {
		while ((p<<ktree)<size-1) {//while pos of child of p < size-1
			int next = -1, min = oo,pj=p<<ktree;
			for (int j=1,k=1<<ktree; j<=k; j++) {
				++pj;
				if (pj>=size) break;
				if (knary[start+pj]<min) { min = knary[start+pj]; next = pj; }
			}//end of for
			if (min>=knary[start+p]) return;
			exchange(start+p, start+next);
			p = next;
		}//end of while
	}

	public void insert(Task x) {
		if (start+size>=LIMIT) expand();
		des[start+size] = x.description;
		knary[start+size] = x.stamp;
		size++;
		goUp(size-1);
		time=0;//reset number of consecutive calls to next() to 0
	}

	public Task next() {
		if (empty()) return null;
		int result = knary[start];
		String rs  = des[start];
		--size;
		if (sorted){
			++start;
			return new Task(rs,result);
		};//end of if
		if ((time++)==lim){
			++start;
			QuickSort(start,start+size-1);
			sorted=true;
			return new Task(rs,result);
		};

		exchange(start,start+size);
		goDown(0);
		return new Task(rs,result);//*/
	}

	public boolean contains(Task x) {
		if (!sorted){
			QuickSort(start,start+size-1);
			sorted=true;
		}
		int key=x.stamp,end=start+size-1,mid=(start+end)/2,s=start;
		String str=x.description;
		if (key==knary[s] && str.equals(des[s])) return true;
		if (key==knary[end] && str.equals(des[end])) return true;

		//Carry out a binary search
		while (s<mid){
			if (knary[mid]>key) end=mid;
			if (knary[mid]<key) s=mid;
			if (knary[mid]==key) break;
			mid=(s+end)/2;
		};//end of while
		if (knary[mid]==key){
			if (des[mid].equals(str)) return true;
			int i=mid-1,j=mid+1;
			while ( i>=start && knary[i]==key){
				if (des[i].equals(str)) return true;
				--i;
			};//end of while
			while ( j<start+size && knary[j]==key){
				if (des[j].equals(str)) return true;
				++j;
			};//end of while
		};
		return false;
	}
}