LRU Cache

Problem statement

A map application keeps a limited cache of recently accessed tiles. When a new tile arrives after the cache fills, it discards the tile that has gone unused for the longest time. Reading or updating a tile makes it recently used. Your task Implement an LRU cache with capacity c. put key value inserts or updates a key; get key returns its value or -1 if absent. Successful get and every put make that key most recently used. Important details Updating an existing key does not increase the entry count. A failed lookup does not alter recency. If insertion exceeds capacity, remove the least recently used key. Each operation must take O(1) average time using a hash map and a doubly linked list. Worked example With capacity 2, put 1 10, put 2 20, get 1, put 3 30, get 2 produces 10 then -1. Reading key 1 makes key 2 the eviction candidate.

Input format

First line: c q. Next q lines: put key value or get key.

Output format

Print one result per get operation, in order. Print EMPTY if there are no get operations.

Constraints

1 <= c <= 3000; 1 <= q <= 200000; 0 <= keys <= 10000; 0 <= values <= 100000.

Sample input

2 5
put 1 10
put 2 20
get 1
put 3 30
get 2

Sample output

10
-1