Implementa un caché con capacidad para \(c\) pares clave-valor que, cuando se llena, descarta el par usado hace más tiempo (least recently used):

• get k: si la clave \(k\) está, imprime su valor y cuenta como uso; si no, imprime \(-1\).
• put k v: guarda \(v\) en la clave \(k\) (si ya estaba, actualiza su valor) y cuenta como uso. Si con esto el caché pasa a tener más de \(c\) claves, descarta la usada hace más tiempo.

Ambas operaciones deben costar \(O(1)\).

Entrada

La primera línea tiene \(c\) \((1 \le c \le 3000)\) y \(q\) \((1 \le q \le 10^5)\), y siguen \(q\) líneas con una operación cada una \((0 \le k \le 10^4,\ 0 \le v \le 10^5)\).

Salida

Una línea por cada get, con su respuesta.

Ejemplo 1

Entrada

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

Salida

1
-1
-1
3
4

Ejemplo 2

Entrada

1 4
get 5
put 5 7
put 5 8
get 5

Salida

-1
8

Basado en el problema 146 de LeetCode, LRU Cache, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.