O(1) Get and Add Data Structure

Given a sequence of operations, implement a data structure where all operations run in amortized O(1) time. You need to support two APIs: get(key): return the value associated with key if it exists; otherwise return -1. add(key, value): insert (key, value) into the data structure; if key already exists, update its value. Requirements: Both operations must be amortized O(1). You may use additional memory. Implement the data structure and provide a main program that reads operations from stdin. Input Format (suggested) The first line contains an integer n, the number of operations. The next n lines are one of: get key add key value Output Format Print one line for each get operation. Constraints 1 <= n <= 2e5 key is a hashable string or integer value is an integer Example Input: 6 add 1 10 add 2 20 get 1 add 1 15 get 1 get 3 Output: 10 15 -1 Example Input 6 add 1 10 add 2 20 get 1 add 1 15 get 1 get 3 Output 10 15 -1