class EvictionPolicy:
    def on_insert(self, key):
        raise NotImplementedError

    def on_access(self, key):
        raise NotImplementedError

    def evict(self):
        raise NotImplementedError


class FIFOPolicy(EvictionPolicy):
    def __init__(self):
        self._order = []

    def on_insert(self, key):
        self._order.append(key)

    def on_access(self, key):
        pass

    def evict(self):
        return self._order.pop(0)


class LRUPolicy(EvictionPolicy):
    def __init__(self):
        self._order = []

    def on_insert(self, key):
        self._order.append(key)

    def on_access(self, key):
        if key in self._order:
            self._order.remove(key)
        self._order.append(key)

    def evict(self):
        return self._order.pop(0)


class LFUPolicy(EvictionPolicy):
    def __init__(self):
        self._counts = {}
        self._order = []

    def on_insert(self, key):
        self._counts[key] = 1
        self._order.append(key)

    def on_access(self, key):
        self._counts[key] = self._counts.get(key, 0) + 1

    def evict(self):
        victim = min(self._order, key=lambda k: self._counts[k])
        self._order.remove(victim)
        del self._counts[victim]
        return victim


class Cache:
    def __init__(self, capacity, policy):
        self.capacity = capacity
        self.policy = policy        # any EvictionPolicy
        self._store = {}

    def get(self, key):
        """Return the value for key, recording an access; None if absent."""
        # TODO: a hit is a key present in self._store. On a hit, tell the policy
        # the key was accessed so recency and frequency stay accurate, then hand
        # back the stored value. A miss tells the policy nothing and yields None.
        pass

    def put(self, key, value):
        """Insert or update key; evict via the policy when over capacity."""
        # TODO: a key already in self._store is an update, overwrite its value,
        # count it as an access on the policy, and never evict. A brand-new key
        # that would take self._store past self.capacity means asking the policy
        # for a victim and dropping it before storing and registering the new key.
        pass