## Problem Design an **in-memory database** that stores values in a nested structure: - `key` (string) → `field` (string) → `value` (string) - Each `(key, field)` entry may optionally have a **TTL** (time-to-live) measured in the same time units as the provided timestamps. - All operations are evaluated **at a given integer timestamp** `ts`. - If an entry is expired at time `ts`, it must behave as if it does not exist. You are given a sequence of queries. Each query is one of the operations below. Implement the database so that each query that produces an output returns the correct string. ### Supported operations Assume all timestamps are non-decreasing across the query list. 1. **Set without TTL** - `SET ts key field value` - Stores `value` at `(key, field)` with **no expiration**. 2. **Set with TTL** - `SET_TTL ts key field value ttl` - Stores `value` at `(key, field)` that is valid on the interval `[ts, ts + ttl)`. 3. **Get** - `GET ts key field` - Returns the stored value, or an empty string `""` if missing/expired. 4. **Delete** - `DELETE ts key field` - Deletes the field if present (and not expired at `ts`). - Returns `"true"` if something was deleted, else `"false"`. 5. **Scan all fields of a key** - `SCAN ts key` - Returns all **non-expired** fields under `key` formatted as: - `field1(value1),field2(value2),...` - Fields must be sorted lexicographically by `field`. - If no fields exist, return an empty string `""`. 6. **Scan fields by prefix** - `SCAN_PREFIX ts key prefix` - Same output format as `SCAN`, but include only fields whose names start with `prefix`. 7. **Backup** - `BACKUP ts` - Creates a **snapshot** of the entire database state **at time `ts`** (including TTL state). - Conceptually, TTL countdown is **paused** in the snapshot: when restoring later, each TTL-based entry should resume with the **remaining TTL it had at backup time**. - (If you need a return value, return the number of top-level keys present in the snapshot; otherwise no output.) 8. **Restore** - `RESTORE ts at_timestamp` - Restores the database to the **most recent snapshot** whose backup time `t_backup` satisfies `t_backup <= at_timestamp`. - After restore at current time `ts`, TTL entries must have their expiration recomputed using the remaining TTL at backup time: - If an entry had expiration `t_exp` originally, then at backup time `t_backup` it had remaining TTL `rem = t_exp - t_backup`. - After restoring at `ts`, its new expiration becomes `ts + rem`. - Entries that were already expired at `t_backup` must not appear in the restored state. - (If you need a return value, return `"true"` if a snapshot was found and restored, else `"false"`.) ## Task Implement a function/class to process the queries in order and return the list of outputs (strings) for the queries that produce outputs (`GET`, `DELETE`, `SCAN`, `SCAN_PREFIX`, and any required outputs for `BACKUP`/`RESTORE` depending on your chosen interface). ## Constraints (typical) - Up to ~10^5 queries - Keys/fields/values are non-empty strings of reasonable length - Timestamps and TTLs fit in 32-bit signed integers - Query timestamps are non-decreasing