AT_abc471_d [ABC471D] Chargers

There is a charger with an unlimited number of charging slots. At time $ 0 $ , all slots are empty. The maximum capacity of a battery is $ V $ . While a battery is plugged into a slot, it is charged at a rate of $ 1 $ until its charge level reaches the maximum capacity (that is, the charge level increases by $ 1 $ for every $ 1 $ unit of time that passes). Process $ Q $ queries in order. The $ q $ -th query is given in one of the following formats. Here, it is guaranteed that $ t_1 < \dots < t_Q $ . - Type $ 1 $ ( $ 1\ t_q\ w_q $ ): At time $ t_q $ , plug one battery with charge level $ w_q $ into a slot. - Type $ 2 $ ( $ 2\ t_q $ ): At time $ t_q $ , unplug one battery with the highest charge level from its slot, and output that battery's charge level. If there is no battery plugged into any slot, output $ -1 $ instead.

The input is given from Standard Input in the following format: > $ Q $ $ V $ $ \mathrm{query}_1 $ $ \vdots $ $ \mathrm{query}_Q $ Here, $ \mathrm{query}_q $ represents the $ q $ -th query, and is given in one of the following two formats: > $ 1 $ $ t_q $ $ w_q $ > $ 2 $ $ t_q $

Let $ x $ be the number of type $ 2 $ queries. Output $ x $ lines. The $ k $ -th line ( $ 1 \leq k \leq x $ ) should contain the value to be outputed for the $ k $ -th type $ 2 $ query.

### Sample Explanation 1 The seven queries are processed in the following order. - At time $ 15 $ , a battery with charge level $ 60 $ is plugged in. At this point, the charger has a battery with charge level $ 60 $ . - At time $ 25 $ , a battery with charge level $ 80 $ is plugged in. At this point, the charger has batteries with charge levels $ 70, 80 $ . - At time $ 30 $ , the charger has batteries with charge levels $ 75, 85 $ . Of these, the battery with charge level $ 85 $ is unplugged. - At time $ 45 $ , a battery with charge level $ 0 $ is plugged in. At this point, the charger has batteries with charge levels $ 0, 90 $ . - At time $ 60 $ , the charger has batteries with charge levels $ 15, 100 $ . Of these, the battery with charge level $ 100 $ is unplugged. - At time $ 70 $ , the charger has a battery with charge level $ 25 $ . This battery, with charge level $ 25 $ , is unplugged. - At time $ 80 $ , no battery is plugged into the charger. Thus, no battery is unplugged. ### Constraints - $ 1 \leq Q \leq 3 \times 10^5 $ - $ 1 \leq V \leq 10^9 $ - For type $ 1 $ queries, $ 1 \leq t_q \leq 10^9 $ . - For type $ 1 $ queries, $ 0 \leq w_q \leq V $ . - For type $ 2 $ queries, $ 1 \leq t_q \leq 10^9 $ . - $ t_1 < \dots < t_Q $ - The input values are all integers.