問題
ここはお店屋さん。人気があるので、頻繁にお客さんが出入りしている(たぶん)。これらのお客さんには、それぞれ 他のお客さんと重複しないような正整数の ID が割り振られている。
私は、一定間隔で売りたくてたまらない商品 i が発作的に頭の中に浮かんでくる。この商品 i を、商品 i の値段以上のお金を所持している店内のお客さんのうち、最小のお金を持つ人 に売ることで、無駄なくお金を使ってもらい、嬉しい気持ちになる。商品 i を売られたお客さんは、必ずその商品を購入し、その商品の値段だけ所持金が減少する。
商品 i を売るべきお客さんの ID を求めて、私の仕事を効率化してね!
入力
入力は以下の形式で与えられる。
N Q p1 p2 : pN Query1 Query2 : QueryQ
1 行目には、私が売りたくなるであろう商品の種類数 N と 与えられるクエリの数 Q が与えられる。
2 行目からは N 行にかけて、商品の値段が与えられる。このうち i (1 ≦ i ≦ N)行目には、i 番目の商品の値段 pi が書かれている。
N + 2 行目からは Q 行にかけて、クエリが時系列順に与えられる。最初、店内には誰もお客さんはいない。このうち i (1 ≦ i ≦ Q)行目には i 番目のクエリ Queryi が次のいずれかの形式で与えられる。
1 ID Money
2 ID
3 Idx
先頭の数字が「1」のとき、お客さん ID が入店したことを表す。また、このお客さんは金額 Money を所持していることが分かっている。店内にいるお客さんのIDが与えられることはないが、一度店に入店し、出店したお客さんのIDが与えられることもある。
先頭の数字が「2」のとき、お客さん ID が出店したことを表す。店内にいないお客さんのIDが与えられることはない。
先頭の数字が「3」のとき、Idx (1 ≦ Idx ≦ N) 番目の商品を売ることを表す。このとき、出力項 の制約に従って解を出力する。また、商品 Idx を売ったあと、売ったお客さんの所持金が pIdx 円減少する。
制約
- 商品の種類数: 1 ≦ N ≦ 1000
- クエリの個数: 1 ≦ Q ≦ 5 × 105
- 商品iの価格: 1 ≦ pi ≦ 109
- お客さんのID: 1 ≦ ID ≦ 109
- お客さんの所持金: 1 ≦ Money ≦ 109
出力
出力はあわせて 複数行(クエリ「3」の個数) になる。所持金が pIdx を超えるお客さんのうち、最小のお金を持つお客さんの ID を出力する。店内に所持金が同じお客さんが複数人いることが考えられるが、その場合 最小の ID を出力する。また、所持金が pIdx を超えるお客さんが存在しない場合は -1 を出力する。
入出力例
入力例１
1 5 100 1 1 100 1 2 101 1 3 101 3 1 3 1
出力例１
1 2
1, 2, 3 番目のクエリで、お金 100 を持つお客さん 1 と、お金 101 を持つお客さん 2 と、お金 102 を持つお客さん 3 が入店する。
4 番目のクエリで、値段 100 の商品を売る。お金 100 を上回り、最小のお金を所持するお客さんは 1 なので、 1 を出力する。お客さん 1 の所持金は 0 となる。
5 番目のクエリで、値段 100 の商品を売る。お金 100 を上回り、最小のお金を所持するお客さんは 2 と 3 だが、ID が小さい方なので 2 を出力する。お客さん 2 の所持金は 1 となる。
入力例2
3 10 100 1 1000002 1 1 101 1 2 1 2 1 3 1 1 1 1000001 1 3 200 3 1 3 1 3 2 3 3
出力例1
-1 3 3 2 -1
1, 2 番目のクエリで、お金 101 を持つお客さん 1 と お金 1 を持つお客さん 2 が入店する。
3 番目のクエリで、お客さん 1 が帰る。
4 番目のクエリで、値段 100 の商品を売ろうとするが、買えるお客さんはいないので -1 を出力する。
5 番目のクエリで、お客さん 1 がたくさんお金を持って戻ってくる。
6 番目のクエリで、お金 200 を持つお客さん 3 が入店する。
7 番目のクエリで、値段 100 の商品を売る。解を満たすお客さんは、ID 3 なので 3 を出力する。お客さん 3 の所持金は 100 となる。
8 番目のクエリでも、値段 100 の商品を売る。解を満たすお客さんは、ID 3 なので 3 を出力する。
9 番目のクエリで、値段 1 の商品を売る。解を満たすお客さんは、ID 2 なので 2 を出力する。
10 番目のクエリで、値段 1000002 の商品を売るが、買えるお客さんはいないので -1 を出力する。
お客さん 1 が可哀想な入力例だった。