Undoable List with kth Smallest Query

You are given a data structure that supports the following operations on a list of integers:

• insert x: Insert the integer \(x\) into the list.
• remove x: Remove one occurrence of the integer \(x\) from the list. If \(x\) does not exist, do nothing.
• kth_smallest k: Output the \(k\)-th smallest integer in the list. If \(k\) is invalid, output None.
• undo: Revert the most recent operation (either an insertion or a removal).

The operations are given as commands through standard input. Your task is to implement the data structure and process the operations accordingly.

Note: The operations should be executed sequentially. For every kth_smallest command, print the result on a new line.

inputFormat

The input begins with an integer (n) indicating the number of operations. Each of the following (n) lines contains a command in one of the following formats:

• insert x • remove x • kth_smallest k • undo

Here, (x) and (k) are integers.

outputFormat

For each kth_smallest command, output the corresponding result on a separate line. If the query is invalid (i.e. the list contains fewer than (k) elements), output None (without quotes).## sample

6
insert 3
insert 1
insert 2
kth_smallest 2
remove 1
kth_smallest 2

2
3