D - Chargers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

無尽蔵の差込口をもつ充電器があります。時刻 0 にはどの差込口も空です。

バッテリーの最大容量は V です。バッテリーは差込口に挿入されているあいだ、残量が最大容量に達するまで速度 1 で充電されます(つまり、1 単位時間が経過するごとに残量が 1 増加します)。

Q 個のクエリを順に処理してください。q 番目のクエリは以下の形式で与えられます。なお、t_1 < \dots < t_Q が保証されます。

  • タイプ 1 (1\ t_q\ w_q): 時刻 t_q に、残量 w_q のバッテリーを 1 つ差込口に挿入する。
  • タイプ 2 (2\ t_q): 時刻 t_q に、最も残量が多いバッテリーを 1 つ差込口から排出し、そのバッテリーの残量を出力する。どの差込口にもバッテリーが無い場合は代わりに -1 を出力する。

制約

  • 1 \leq Q \leq 3 \times 10^5
  • 1 \leq V \leq 10^9
  • タイプ 1 のクエリにおいて、1 \leq t_q \leq 10^9
  • タイプ 1 のクエリにおいて、0 \leq w_q \leq V
  • タイプ 2 のクエリにおいて、1 \leq t_q \leq 10^9
  • t_1 < \dots < t_Q
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

Q V
\mathrm{query}_1
\vdots
\mathrm{query}_Q

ここで、\mathrm{query}_q は q 番目のクエリを表し、以下の 2 種類のいずれかの形式で与えられる。

1 t_q w_q

2 t_q

出力

タイプ 2 のクエリの個数を x として、x 行出力せよ。

k 行目 (1 \leq k \leq x) には、k 番目のタイプ 2 のクエリで出力するべき値を出力せよ。

入力例 1

7 100
1 15 60
1 25 80
2 30
1 45 0
2 60
2 70
2 80

出力例 1

85
100
25
-1

7 個のクエリを以下の順に処理します。

  • 時刻 15 に、残量 60 のバッテリーを挿入する。この時点で、残量 60 のバッテリーが充電器にある。
  • 時刻 25 に、残量 80 のバッテリーを挿入する。この時点で、残量 70, 80 のバッテリーが充電器にある。
  • 時刻 30 の時点で、残量 75, 85 のバッテリーが充電器にある。このうち、残量 85 のバッテリーを排出する。
  • 時刻 45 に、残量 0 のバッテリーを挿入する。この時点で、残量 0, 90 のバッテリーが充電器にある。
  • 時刻 60 の時点で、残量 15, 100 のバッテリーが充電器にある。このうち、残量 100 のバッテリーを排出する。
  • 時刻 70 の時点で、残量 25 のバッテリーが充電器にある。このうち、残量 25 のバッテリーを排出する。
  • 時刻 80 の時点で、充電器に挿入されたバッテリーは無い。そのため、バッテリーの排出はしない。

入力例 2

20 380736236
1 21873985 256702097
2 86369729
1 114301317 288304981
1 147244640 305840435
2 150951976
1 331581391 50335458
1 352989552 47577202
1 400130024 345362760
2 458793150
2 509082216
1 591375600 197371572
1 617022014 101276068
1 679649471 310249627
1 796351653 268586022
1 825648347 129608152
2 908069704
2 921770319
1 949684819 372272469
1 971850999 335461408
2 986253026

出力例 2

321197841
324955640
380736236
380736236
380736236
380736236
380736236

Score : 400 points

Problem Statement

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.

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.

Input

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

Output

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 Input 1

7 100
1 15 60
1 25 80
2 30
1 45 0
2 60
2 70
2 80

Sample Output 1

85
100
25
-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.

Sample Input 2

20 380736236
1 21873985 256702097
2 86369729
1 114301317 288304981
1 147244640 305840435
2 150951976
1 331581391 50335458
1 352989552 47577202
1 400130024 345362760
2 458793150
2 509082216
1 591375600 197371572
1 617022014 101276068
1 679649471 310249627
1 796351653 268586022
1 825648347 129608152
2 908069704
2 921770319
1 949684819 372272469
1 971850999 335461408
2 986253026

Sample Output 2

321197841
324955640
380736236
380736236
380736236
380736236
380736236