Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Missing Order

By humayan7711 · Limits 1s, 512 MB

It's IIKI's birthday today. He got a function called INSERTER as a gift from OIIKI, one of his mathematician friends. Initially, he has an empty array. With the function, he can perform the following operations on this array.

• 1 x idx — insert value x at index idx
• 2 k idx — insert k-th smallest element of the array at index idx

IIKI performed $Q$ operations and informed you details of each operation. Can you print the final array?
Note that, first operation is always of first type.

Input

The first line contains one integer $Q$ — the number of operations performed. Each of the following $Q$ lines contains the description of the operation.

Constraints

• $1\leqslant$ $Q \leqslant 2×10^5$
• $1\leqslant$ $x \leqslant 10^9$
• $1\leqslant$ $k \leqslant array.size()\ before\ operation\$
• $0\leqslant$ $idx \leqslant array.size()\ before\ operation\$

Output

Print the final array after performing all the operations.

Sample

InputOutput
5
1 7 0
1 5 1
2 2 2
2 1 0
1 3 2

5 7 3 5 7


Statistics

17% Solution Ratio

YouKnowWhoEarliest, Aug '20

YouKnowWhoFastest, 0.4s

NJRafiLightest, 22 MB

YouKnowWhoShortest, 3097B