"""Two cache eviction policies, side by side: LRU (least-recently-used) and
LFU (least-frequently-used). Both expose the same interface — get(key) and
put(key, value) — and both count hits, misses and evictions.

Neither reads a clock nor an RNG. Eviction order is a pure side effect of the
data structure: for LRU, position in a doubly linked list; for LFU, an
integer count plus insertion order within a count. Same trace, same numbers,
every run.
"""


class Node:
    """One entry in the LRU cache's doubly linked list.

    Nodes are also used as the two sentinels, which is why key and value
    default to None: a sentinel is a node that is never in the map.
    """

    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    """A dict from key -> Node, plus a doubly linked list of those nodes kept
    in most-recently-used-first order.

    The list *is* the policy. head.next is the most recently used entry;
    tail.prev is the next victim. The dict makes lookup O(1); the two links
    make "move this entry to the front" O(1) without scanning anything.
    """

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        # Sentinel head and tail. They hold no data; they exist so _unlink
        # and _push_front never have to check for None neighbours, which is
        # where every hand-written linked list goes wrong.
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.hits = 0
        self.misses = 0
        self.evictions = 0

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            self.misses += 1
            return None
        self.hits += 1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) >= self.capacity:
            victim = self.tail.prev
            self._unlink(victim)
            del self.map[victim.key]
            self.evictions += 1
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

    def keys(self):
        """Residents, most recently used first — i.e. eviction order reversed."""
        out = []
        node = self.head.next
        while node is not self.tail:
            out.append(node.key)
            node = node.next
        return out


class LFUCache:
    """A dict from key -> value, a dict from key -> access count, and one
    bucket per count holding the keys that currently have it.

    Each bucket is a dict used as an insertion-ordered set, so ties are
    broken deterministically: among keys with the same count, the one that
    arrived at that count first is evicted. min_count is maintained
    incrementally, which is what keeps eviction O(1) rather than a min() over
    every resident key.
    """

    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}
        self.counts = {}
        self.buckets = {}  # count -> {key: None}, insertion-ordered
        self.min_count = 0
        self.hits = 0
        self.misses = 0
        self.evictions = 0

    def _bump(self, key):
        count = self.counts[key]
        bucket = self.buckets[count]
        del bucket[key]
        if not bucket:
            del self.buckets[count]
            # The only bucket that can empty and matter is the minimum one,
            # and the key that just left it went to exactly count + 1.
            if self.min_count == count:
                self.min_count = count + 1
        self.counts[key] = count + 1
        self.buckets.setdefault(count + 1, {})[key] = None

    def get(self, key):
        if key not in self.values:
            self.misses += 1
            return None
        self.hits += 1
        self._bump(key)
        return self.values[key]

    def put(self, key, value):
        if key in self.values:
            self.values[key] = value
            self._bump(key)
            return
        if len(self.values) >= self.capacity:
            bucket = self.buckets[self.min_count]
            victim = next(iter(bucket))
            del bucket[victim]
            if not bucket:
                del self.buckets[self.min_count]
            del self.values[victim]
            del self.counts[victim]
            self.evictions += 1
        self.values[key] = value
        self.counts[key] = 1
        self.buckets.setdefault(1, {})[key] = None
        # A brand-new key has count 1, so the minimum is 1 again. Forgetting
        # this line is the classic LFU bug: min_count drifts upward and the
        # cache evicts a frequently used key while a fresh one sits at 1.
        self.min_count = 1

    def keys(self):
        """Residents, lowest count first — i.e. eviction order."""
        out = []
        for count in sorted(self.buckets):
            out.extend(self.buckets[count])
        return out