LRU Cache Query Processor

You are given a series of queries to simulate an LRU (Least Recently Used) Cache. The cache has a fixed capacity \(n\). It supports the following two operations:

• Put: Insert or update a key with a given value. When the cache exceeds its capacity, it removes the least recently used key.
• Get: Retrieve the value associated with a key. If the key does not exist, return \(-1\).

You are required to process \(m\) queries. For each query of type 2 (get queries), output the result on a separate line.

inputFormat

The input is given via stdin in the following format:

n m
q1
q2
...
qm

Here, the first line contains two integers \(n\) and \(m\) where \(n\) is the capacity of the cache and \(m\) is the number of queries. Each of the next \(m\) lines represents a query in one of the following forms:

• 1 key value : A put operation that inserts or updates the key with the given value.
• 2 key : A get operation that retrieves the value associated with the key. If the key does not exist, output \(-1\).

outputFormat

For each query of type 2, output the result on a new line via stdout.

## sample

3 7
1 1 10
1 2 20
2 1
1 3 30
2 2
1 4 40
2 1

10
20
-1

</p>