RandomizedSet: O(1) Insert, Remove, and Get Random

You are required to design a data structure RandomizedSet that supports insert, remove and get_random operations in average O(1) time.

The data structure should implement the following operations:

• insert x: Inserts an element x into the set. Returns True if the element was not present and was inserted successfully, otherwise returns False.
• remove x: Removes an element x from the set. Returns True if the element was present and removed, otherwise returns False.
• get_random: Returns a random element from the current set. It is guaranteed that there will be at least one element in the set when this operation is called.

All operations should run in average O(1) time complexity. One possible design uses a combination of a dynamic array and a hash map (or dictionary) to achieve this efficiency.

In terms of algorithm analysis, if the size of the set is n, then each operation should run in O(1) on average. In mathematical notation, for insert and remove operations, we expect:

[ O(1)\quad\text{amortized}, ]

while get_random should also operate in O(1) time.

inputFormat

The input is given through standard input (stdin). The first line contains an integer n (1 ≤ n ≤ 10⁴), representing the number of operations. Each of the following n lines represents an operation and is in one of the following formats:

• insert x where x is an integer.
• remove x where x is an integer.
• get_random

For each operation, you should output the result on a new line. The results for insert and remove operations are True or False (case-sensitive), and for the get_random operation, output the selected integer.

outputFormat

Output the result of each operation in the order they are given, each on a separate line. For insert and remove, output True or False. For get_random, output the integer value returned.

## sample

5
insert 1
insert 2
get_random
remove 1
get_random

True
True
2
True
2

</p>