Task

Simulate an LRU (Least Recently Used) cache. The cache has a fixed capacity. On a PUT(key, value) operation: if the key already exists, update its value and mark it as most recently used (no miss counted); if it is a new key, count a miss, insert it, and evict the least recently used entry if the cache is at capacity. On a GET(key) operation: if the key is in the cache, mark it as most recently used and return its value; otherwise return -1 (GET misses are not counted).

Input

• Line 1: capacity q — cache capacity and number of operations
• Lines 2 to q+1: either GET key or PUT key value

Output

Print the result of each GET operation (one per line), then print misses: N where N is the total count of PUT misses (new-key insertions).

Example

Input:

2 5
PUT 1 10
PUT 2 20
GET 1
PUT 3 30
GET 2

Output:

10
-1
misses: 3

Scaffolding

Submit a Python file defining:

def lru_sim(capacity: int, ops: list[tuple]) -> tuple[list[int], int]:
    ...

Receives the cache capacity and a list of operations as tuples ('GET', key) or ('PUT', key, value); returns a tuple of (get_results, miss_count) where get_results is the list of values returned by GET operations and miss_count is the number of new-key PUT insertions.