Randomized Collection

You are given a data structure that supports the following operations in average O(1) time:

• Insert: Insert an integer into the collection.
• Remove: Remove one occurrence of an integer from the collection (if it exists).
• getRandom: Return a random element from the current collection.

The operations are encoded as queries. Each query is one of the following types:

• 1 x — Insert integer x into the collection.
• 2 x — Remove one occurrence of integer x from the collection.
• 3 — Output a random element from the collection (each such query prints one line).

For the purpose of testing, you should initialize the random number generator with a fixed seed so that the behavior is deterministic. In our provided sample solutions, this is accomplished by seeding the random number generator with 0 (or an equivalent technique in other languages).

Your task is to implement the data structure and process all queries accordingly.

inputFormat

The input is given from standard input. The first line contains an integer Q, representing the number of queries. The following Q lines each contain a query. A query of type 1 and type 2 consists of two space-separated integers (the query type and the value). A query of type 3 consists of a single integer (3).

outputFormat

For each query of type 3, output the returned integer on a new line to standard output.## sample

7
1 10
1 20
3
1 30
2 20
3
3

20
30
10