If the sorted array of all the values in the set is {ai} n

i=1, let t = ⌈n/2⌉, then the median 2k values are

{at−k+1, · · · , at+k}.

Barbara has got a set of values with size of 2k initially. Barbara wants to do m operations on it. Each

operation belongs to the following 3 types:

• 1 w: insert a value w.
• 2: output all the median 2k values, i.e. at−k+p, ∀1 ≤ p ≤ 2k.
• 3 p: delete the p-th value among median 2k values, i.e. at−k+p.

We guarantee that all the values will be distinct and the size of the set is always at least 2k.