Design data structure similar to LRU cache

You are asked to design and implement a data structure that behaves similarly to an LRU (Least Recently Used) cache, but with a small variation:

• The data structure stores key–value pairs.
• It has a fixed capacity capacity .
• When inserting a new key and the cache is full, it should evict an existing key according to a modified eviction rule (a variant of LRU). For example, assume the rule is:
  • Normally evict the least recently used key, except that keys explicitly "pinned" by the user should not be evicted until they are unpinned.

Your data structure must support the following operations in average O(1) time:

• get(key) -> value or -1
  Return the value associated with key if it exists; otherwise return -1 . Accessing a key counts as using it recently.
• put(key, value)
  Insert or update the value of key . If inserting and the number of stored keys exceeds capacity , evict one key according to the modified eviction rule described above.
• pin(key)
  Mark an existing key as pinned so that it cannot be evicted while pinned.
• unpin(key)
  Remove the pinned status from a key so that it can again be evicted according to the LRU policy.

Assume:

• 1 <= capacity <= 10^5
• Keys and values are integers.
• The total number of operations is up to 10^5 .

Describe the data structure you would use and implement the four operations with the required time complexity.