// Runtime: 31 ms, faster than 90.52% of Java online submissions for Design HashMap.
// Memory Usage: 57.5 MB, less than 35.14% of Java online submissions for Design HashMap.
class MyHashMap {
    int p;
    int size;
    List<Entry>[] table;

    /** Initialize your data structure here. */
    public MyHashMap() {
        p = 37;
        size = 0;
        table = new List[p];
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        List<Entry> list = table[key % p];
        if (list == null) {
            list = new LinkedList<Entry>();
            table[key % p] = list;
        }

        for (Entry e: list)
            if (e.key == key) {
                e.value = value;
                return;
            }

        if (size >= p) {
            resize();
            put(key, value);
        } else {
            list.add(new Entry(key, value));
            size++;
        }
    }

    private void resize() {
        List<Entry>[] oldTable = table;

        p = 2*p + 1;
        size = 0;
        table = new List[p];

        for (List<Entry> list: oldTable) {
            if (list == null) continue;
            for (Entry entry: list) {
                put(entry.key, entry.value);
            }
        }
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        List<Entry> list = table[key % p];
        if (list == null) return -1;

        for (Entry e: list)
            if (e.key == key) return e.value;

        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        List<Entry> list = table[key % p];
        if (list == null) return;

        ListIterator<Entry> iterator = list.listIterator();
        while (iterator.hasNext()) {
            Entry entry = iterator.next();
            if (entry.key == key) {
                iterator.remove();
                size--;
                return;
            }
        }
    }

    class Entry {
        public int key;
        public int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */