Implement a Two-level Storage System with Expiry and Checkpoint

Problem Description Implement a two-level storage system supporting the following functionalities: Basic Operations: Implement get, set, update, and delete operations. Two-level Storage: Implement using a map<string, map<string, string>> structure, where each outer key corresponds to an inner key-value pair. Expiry Time: Support storing data with an expiry time. Record the timestamp when storing data and check its expiry upon retrieval. Conditional Retrieval: Provide an interface to find all values starting with a specified prefix. Checkpoint: Implement checkpoints and allow rolling back to a specific checkpoint. Provide detailed descriptions for each functionality along with complete code and test cases. Input/Output Requirements Implement the following interfaces: set(key: str, sub_key: str, value: str, expiry_time: int) -> None get(key: str, sub_key: str) -> str | None update(key: str, sub_key: str, value: str) -> bool delete(key: str, sub_key: str) -> bool find_by_prefix(prefix: str) -> List[str] checkpoint() -> int rollback_to_checkpoint(id: int) -> bool Example storage = TwoLevelStorage() storage.set("user1", "session1", "data1", 3600) assert storage.get("user1", "session1") == "data1" storage.update("user1", "session1", "data2") assert storage.get("user1", "session1") == "data2" storage.delete("user1", "session1") assert storage.get("user1", "session1") is None storage.set("user2", "session1", "example", 3600) storage.set("user2", "session2", "test", 3600) assert storage.find_by_prefix("exa") == ["example"] checkpoint_id = storage.checkpoint() storage.set("user2", "session3", "temporary", 3600) # This will restore state to before "session3" was added storage.rollback_to_checkpoint(checkpoint_id) assert storage.get("user2", "session3") is None Constraints and Test Cases Each API can be called up to 10^5 times Each value's length is no more than 100 characters Total storage size is no more than 10^6 key-value pairs Example Input set user1 session1 data1 3600