Симуляция LRU-кеша

Реализуйте LRU-кеш ёмкости c. Операции:

• put key value записывает значение; если ключа не было и кеш полон, сначала вытесняется ключ, к которому дольше всего не обращались;
• get key выводит значение или -1; успешный get считается обращением.

put существующего ключа обновляет значение и тоже считается обращением.

Ввод: в первой строке c и q (1 ≤ c ≤ 10⁴, 1 ≤ q ≤ 2·10⁴), далее q операций. Ключи и значения целые от 0 до 10⁹.

Вывод: результат каждого get на отдельной строке.

Пример

2 9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

1
-1
-1
3
4