LRU-кеш на list и unordered_map

Реализуйте LRU-кеш ёмкости cap со строковыми ключами и числовыми значениями:

• get k: вывести значение по ключу или -1; при попадании ключ становится самым свежим;
• put k v: записать значение (ключ становится самым свежим); если ключей стало больше cap, удалить самый давно использованный.

Обе операции должны работать за O(1) в среднем.

Ввод: cap и q (1 ≤ cap ≤ 1000, 1 ≤ q ≤ 3000), затем q команд. Ключи из латинских букв и цифр до 10 символов, 1 ≤ v ≤ 10⁶.

Вывод: ответы на get, каждый с новой строки.

Пример 1

Ввод:

2 7
put a 1
put b 2
get a
put c 3
get b
get c
get a

Вывод:

1
-1
3
1

Пример 2

Ввод:

1 4
get x
put x 5
put x 6
get x

Вывод:

-1
6