LRU-кеш

Реализуйте LRU-кеш ёмкостью cap. GET k возвращает значение и делает ключ самым свежим (или -1, если ключа нет). PUT k v добавляет или обновляет значение и делает ключ самым свежим; если ключ новый и кеш полон, сначала вытесняется давно не использованный.

Ввод: cap q (1 ≤ cap ≤ 10⁴, q ≤ 2·10⁴), затем q команд. Ключи из латиницы и цифр, значения целые.

Вывод: результат каждого GET на отдельной строке. Все операции должны работать за O(1).

Пример

2 7
PUT a 1
PUT b 2
GET a
PUT c 3
GET b
GET c
GET a

1
-1
3
1