// Runtime: 57 ms, faster than 89.47% of Java online submissions for Design HashMap.
// Memory Usage: 54.5 MB, less than 43.24% of Java online submissions for Design HashMap.
class MyHashMap {
    int p;
    List<Entry>[] table;

    /** Initialize your data structure here. */
    public MyHashMap() {
        p = 37;
        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;
            }

        list.add(new Entry(key, 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();
                return;
            }
        }
    }

    class Entry {
        public int key;
        public int value;

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