Design an LRUCacheWithTimeConstraint class that implements an LRU cache with a fixed capacity and a time constraint.

The cache stores key-value pairs.

Each key-value pair remains valid only for a fixed number of seconds after it is inserted or updated.

If a key is accessed after its valid time has expired, it must be treated as missing from the cache.

When the cache exceeds its fixed capacity, the least recently used valid key must be removed.

A successful get operation makes that key the most recently used key.

A put operation also makes the inserted or updated key the most recently used key.

Before processing any operation, all expired keys must be considered unavailable.

LRUCacheWithTimeConstraint(int capacity, int ttlSeconds)

• Initializes the cache with a fixed maximum capacity.
• Each key remains valid for exactly ttlSeconds seconds after its latest put operation.

void put(String key, String value, int currentTime)

• Inserts a new key-value pair into the cache.
• If the key already exists and is not expired, update its value and refresh its expiry time.
• If the key already exists but is expired, remove the expired entry first and insert it as a new key.
• The key becomes the most recently used key after this operation.

String get(String key, int currentTime)

• Returns the value stored for the key if the key exists and is not expired.
• Returns "NOT_FOUND" if the key does not exist or has expired.
• A successful get makes the key the most recently used key.

If a key is inserted or updated at time t, then it is valid for all calls where:
currentTime < t + ttlSeconds

The key is expired when:
currentTime >= t + ttlSeconds

After removing expired keys, if inserting a new key causes the number of valid keys to become greater than capacity, remove the least recently used valid key.

Recency is updated only by:

• A successful get operation.
• A put operation that inserts or updates a key.

• currentTime is in seconds and is monotonically increasing (non-decreasing) across all methods.
• If multiple operations happen at the same currentTime, their recency is determined by method call order. A later method call is more recent than an earlier method call.
• Expired keys must not be returned by get.
• Expired keys must not count toward cache capacity.
• Calling get on an expired key removes it from the cache and returns "NOT_FOUND".
• Calling put on an expired key inserts it again with a new expiry time.
• The value "NOT_FOUND" is reserved and will not be used as an input value.
• No parameter value will be null.

• 1 ≤ capacity ≤ 105
• 1 ≤ ttlSeconds ≤ 106
• 1 ≤ key.length() ≤ 50
• 1 ≤ value.length() ≤ 50
• 0 ≤ currentTime ≤ 109
• At most 105 method calls will be made.
• key and value contain only lowercase English letters, uppercase English letters, digits, hyphen, and underscore.
• value will never be "NOT_FOUND".

LRUCacheWithTimeConstraint cache = new LRUCacheWithTimeConstraint(capacity = 2, ttlSeconds = 5);
cache.put(key = "A", value = "Apple", currentTime = 1);
cache.put(key = "B", value = "Banana", currentTime = 2);
cache.get(key = "A", currentTime = 3) returns "Apple"
cache.put(key = "C", value = "Cherry", currentTime = 4);
cache.get(key = "B", currentTime = 4) returns "NOT_FOUND"

Explanation:
The cache capacity is 2.
Key "A" is accessed at time 3, so it becomes the most recently used key.
When key "C" is inserted at time 4, key "B" is the least recently used valid key, so it is removed.

LRUCacheWithTimeConstraint cache = new LRUCacheWithTimeConstraint(capacity = 2, ttlSeconds = 3);
cache.put(key = "A", value = "Apple", currentTime = 10);
cache.get(key = "A", currentTime = 12) returns "Apple"
cache.get(key = "A", currentTime = 13) returns "NOT_FOUND"

Explanation:
Key "A" is inserted at time 10.
Since ttlSeconds = 3, it is valid while currentTime < 13.
At time 13, the key has expired and must return "NOT_FOUND".

LRUCacheWithTimeConstraint cache = new LRUCacheWithTimeConstraint(capacity = 2, ttlSeconds = 5);
cache.put(key = "A", value = "Apple", currentTime = 1);
cache.put(key = "B", value = "Banana", currentTime = 2);
cache.put(key = "A", value = "Apricot", currentTime = 4);
cache.get(key = "A", currentTime = 8) returns "Apricot"
cache.get(key = "B", currentTime = 8) returns "NOT_FOUND"
cache.get(key = "A", currentTime = 9) returns "NOT_FOUND"

Explanation:
Key "A" is updated at time 4, so its value becomes "Apricot" and its expiry time is refreshed.
Key "A" remains valid while currentTime < 9.
Key "B" was inserted at time 2, so it expires at time 7.

LRUCacheWithTimeConstraint cache = new LRUCacheWithTimeConstraint(capacity = 1, ttlSeconds = 10);
cache.put(key = "A", value = "Apple", currentTime = 1);
cache.put(key = "B", value = "Banana", currentTime = 2);
cache.get(key = "A", currentTime = 3) returns "NOT_FOUND"
cache.get(key = "B", currentTime = 3) returns "Banana"

Explanation:
The cache capacity is 1.
When key "B" is inserted, key "A" is the least recently used valid key and is removed.