Implement an in-memory storage with TTL and scans

## Problem Implement an in-memory storage system similar to a tiny key–field–value database. - Data model: a **2-level map** `key -> field -> value`. - Each operation includes a **timestamp** `ts` (non-decreasing across the input). - A `(key, field)` entry may optionally have a **TTL** (time-to-live), after which it is considered **expired** and must behave as if it does not exist. You will be given a sequence of queries/commands. Process them in order and return outputs for the commands that produce an output. ## Commands Assume all `key`, `field`, `value`, `prefix` are non-empty strings without spaces; `ts` and `ttl` are integers. ### Basic operations (Level 1) 1. `SET ts key field value` - Set `value` for `(key, field)` at time `ts`. - This write has **no TTL** (never expires) and overwrites any previous value/TTL. 2. `GET ts key field` - Return the current value of `(key, field)` at time `ts`. - If missing or expired, return an empty string `""`. 3. `COMPARE_AND_SET ts key field expected newValue` - If the current (non-expired) value equals `expected`, set it to `newValue` (no TTL) and return `"true"`. - Otherwise return `"false"`. 4. `COMPARE_AND_DELETE ts key field expected` - If the current (non-expired) value equals `expected`, delete the field and return `"true"`. - Otherwise return `"false"`. ### Scans (Level 2) 5. `SCAN ts key` - Return all non-expired fields for `key`, **sorted lexicographically by field name**. - Format each as `field(value)` and join with commas, e.g. `a(1),b(2)`. - If `key` has no non-expired fields, return `""`. 6. `SCAN_BY_PREFIX ts key prefix` - Same as `SCAN`, but include only fields whose name starts with `prefix`. ### TTL support (Level 3) 7. `SET_WITH_TTL ts key field value ttl` - Set `value` for `(key, field)` at time `ts` with expiration time `expireAt = ts + ttl`. - The entry is considered valid for timestamps `t` such that `ts <= t < expireAt`. - Overwrites any previous value/TTL. **TTL rule:** At timestamp `ts`, an entry is visible only if it exists and is not expired at `ts`. ### Time-travel queries (Level 4 / advanced) 8. `GET_AT ts key field atTs` - Return the value that `(key, field)` had at time `atTs` (with TTL and deletes respected). - If it did not exist or was expired at `atTs`, return `""`. - You may assume `atTs <= ts`. ## Input / Output - Input: `queries`, a list where each element is a list of strings describing one command (tokens in the order shown above). - Output: a list of strings containing the results of each command that produces output: - `GET`, `COMPARE_AND_SET`, `COMPARE_AND_DELETE`, `SCAN`, `SCAN_BY_PREFIX`, `GET_AT`. - `SET` and `SET_WITH_TTL` produce no output. ## Constraints (typical interview scale) - `1 <= len(queries) <= 100000` - Timestamps are non-decreasing. - Total length of all strings is manageable in memory. Implement the function that processes the queries and returns the output list.