import java.util.*;

class SkipList<K extends Comparable<K>,V> extends AbstractMap<K,V> {
    private int size, levels;
    private Term current;

    class Term implements Entry<K, V>{

        private K key;
        private V value;
        private Term[] next;

        private Term(K key, V value){
            this.key = key;
            this.value = value;
            this.next = new SkipList.Term[levels];
        }

        @Override
        public K getKey() {
            return this.key;
        }

        @Override
        public V getValue() {
            return this.value;
        }

        @Override
        public V setValue(V value) {
            this.value = value;
            return value;
        }

        public Term[] getNext() {
            return next;
        }
    }
    public SkipList(int levels){
        this.levels = levels;
        this.size = 0;
        this.current = new Term(null, null);
    }


    @Override
    public void clear() {
        this.size = 0;
        this.current = new Term(null, null);
    }

    public V remove(K key){
        Term p[] = Skip(key);
        Term help = p[0].next[0];
        V temp = help.value;
        if(help == null || help.key.equals(key) == false) return null;
        for(int i = 0; i < levels && p[i].next[i] == help; p[i].next[i] = help.next[i], i++);
        size--;
        return temp;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return new MyEntrySet();
    }

    private class MyEntrySet extends AbstractSet{
        public Iterator<SkipList<K, V>> iterator(){
            return new MyIterator();
        }

        private class MyIterator implements Iterator{
            private Term i = current;
            @Override
            public boolean hasNext() {
                return i.getNext()[0] != null;
            }

            @Override
            public Term next() {
                i = i.getNext()[0];
                return i;
            }

            @Override
            public void remove(){
                SkipList.this.remove(i.getKey());
            }
        }

        @Override
        public int size() {
            return size;
        }
    }

    public  Term[] Skip(K key){
        Term[] p = new SkipList.Term[levels];
        Term x = current;
        for(int i = levels -1; i >= 0; i--){
            while(x.next[i] != null && x.next[i].key.compareTo(key) < 0){
                x = x.next[i];
            }
            p[i] =  x;
        }
        return p;
    }

    public V put(K key, V value){
        Term[] p =  Skip(key);
        Term x = new Term(key, value);
        Random random = new Random();
        int i, randdigit = random.nextInt() * 2;
        if (p[0].next[0] != null && p[0].next[0].key == key) {
            V help = p[0].next[0].value;
            p[0].next[0].setValue(value);
            return help;
        }
        for(i = 0; i < levels && randdigit % 2 == 0; i++, randdigit >>= 2){
            x.next[i] =  p[i].next[i];
            p[i].next[i] = x;
        }
        for(; i < levels;x.next[i] = null, i++);
        size ++;
        return null;
    }
}