Задача на Swift: LRU-кеш для картинок

Реализуйте LRU-кеш ёмкостью cap: при переполнении удаляется элемент, к которому дольше всего не обращались. Обращением считаются get с попаданием и put.

• put k v: записать значение (если ключ есть, обновить и сделать самым свежим);
• get k: вывести значение и сделать ключ самым свежим, или miss.

Первая строка: cap n (1 ≤ cap ≤ 10⁵, 1 ≤ n ≤ 10⁴). Дальше n команд. Ключи и значения без пробелов.

Пример

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

1
miss
1
3

После get a самый старый b, его и вытесняет put c.