There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The concatenation of all the chunks should result in a list of the sorted values.

Implement the OrderedStream class:

OrderedStream(n: int) Constructs the stream to take n values.

insert(idKey: int, value: str) -> List[str] Inserts the pair (idKey, value) into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order.

class OrderedStream:

    def __init__(self, n: int):


    def insert(self, idKey: int, value: str):



# Note that the following code is for local testing purposes only. You should leave this part of code unchanged and not submit it to the OJ system.
stream = OrderedStream(5)
print(stream.insert(3, "ccccc"))
print(stream.insert(1, "aaaaa"))
print(stream.insert(2, "bbbbb"))
print(stream.insert(5, "eeeee"))
print(stream.insert(4, "ddddd"))

Please note that you only have to submit the definition of the OrderedStream class to the OJ system. The rest of the code is for your local testing purposes only.

Input Specification

The sample input shows how we will call your code. For each testcase exactly ~1~ function call will be made to init, and exactly ~\mathbf{n}~ calls will be made to insert.

Limits

Memory limit: 32 MB.

Time limit: 1 second.

~1 \le \mathbf{n} \le 1000~

~1 \le \mathbf{\text{id}} \le \mathbf{n}~

~\text{length of value} == 5~

Output Specification

For each function call, you must return exactly what we asked for.

Sample Input

stream = OrderedStream(5)
stream.insert(3, "ccccc")
stream.insert(1, "aaaaa")
stream.insert(2, "bbbbb")
stream.insert(5, "eeeee")
stream.insert(4, "ddddd")

Sample Output (Return value)

[]                  # Inserts (3, "ccccc"), returns [].
['aaaaa']           # Inserts (1, "aaaaa"), returns ["aaaaa"].
['bbbbb', 'ccccc']  # Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
[]                  # Inserts (5, "eeeee"), returns [].
['ddddd', 'eeeee']  # Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Example