import java.util.*;

class FreqRank {

    protected HashMap<String,Integer> str2int;
    protected HashMap<Integer,String> int2str;
    int maxIndex;

    public FreqRank() {
	str2int = new HashMap<String,Integer>();
	int2str = new HashMap<Integer,String>();
	maxIndex = 0;
    }

    public FreqRank(Scanner in) {
	this();
	while (in.hasNextLine()) {
	    add(in.nextLine());
	}
    }

    public String toString() {
	String s = "";
	for (int i = 0; i < maxIndex; i++) {
	    s += int2str.get(i);
	    s += "\n";
	}
	return s;
    }

    public Integer getIndex(String s) {
	Integer ret = null;
	try {
	    ret = str2int.get(s);
	} catch (NullPointerException e) {
	    return null;
	}
	return ret;
    }

    public String getString(int n) {
	return int2str.get(n);
    }

    public int size() {
	return maxIndex;
    }

    //Adds the given string at the least possible frequency.
    public boolean add(String s) {
	if (str2int.get(s) != null) {
	    return false;
	}
	str2int.put(s,maxIndex);
	int2str.put(maxIndex,s);
	maxIndex++;
	return true;
    }

    // Promotes the frequency of string s by num ranks.  Takes O(num) time.
    public void promote(String s, int num) {
	if (num == 0) {
	    return;
	}

	int index = str2int.get(s);
	str2int.remove(s);
	int2str.remove(index);
	String swap = int2str.get(index-1);
	str2int.remove(swap);
	int2str.remove(index-1);

	str2int.put(s, index-1);
	int2str.put(index-1, s);
	str2int.put(swap, index);
	int2str.put(index, swap);

	promote(s, num-1);
    }

}