Implementing an LRU Web Cache

You are required to implement an LRU (Least Recently Used) cache for web pages. The cache holds web pages where each page is represented as a URL and its corresponding HTML content. The cache has a fixed capacity, and if it becomes full, it should remove the least recently used entry before inserting a new one.

The cache should support two operations:

• set: Insert or update the content for a given URL. If the URL already exists, update its content and mark it as the most recently used.
• get: Retrieve the content corresponding to a given URL. If the URL is not present, output URL not found.
</p>

Note: When a URL is accessed by either get or set, it should become the most recently used item. Use the following LaTeX formatted eviction rule: When the cache is full, remove the item with the smallest recency value, i.e. \( \min(\text{recency}) \).

inputFormat

The input is read from stdin and has the following format:

capacity
Q
command_1
[argument(s) for command_1]
command_2
[argument(s) for command_2]
...
command_Q
[argument(s) for command_Q]

The first line is an integer capacity representing the maximum number of items the cache can hold. The second line is an integer Q representing the number of commands. Each subsequent command is either:

• For a set command, three lines: a line with the word set, a line with the URL string, and a line with the HTML content.
• For a get command, two lines: a line with the word get and a line with the URL string.

outputFormat

For each get command, output the corresponding content (or URL not found if the URL is not in the cache) on a separate line to stdout.

## sample

2
3
set
http://example.com
Example
get
http://example.com
get
http://nonexistent.com

Example
URL not found

</p>