データ構造II

2 secs 1024 MB
Tonegawac

問題文


はじめに、全ての要素が異なる要素数 の集合 が与えられる。
この集合に対し、以下の形式で 回与えられる操作を処理せよ。

  • : 集合に を追加する (クエリを行う時点で集合に が無いことが保証される)
  • : 集合から を削除する (クエリを行う時点で集合に が含まれることが保証される)
  • : 集合の要素の中で 番目(0-indexed)に小さい値を出力する (クエリを行う時点で集合にk+1種類以上の要素が含まれることが保証される)
  • : 集合の要素の中で よりも真に小さい要素の数を出力する

制約


  • 入力は全て整数である。

入力


N Q
A_0 A_1 A_2 ... A_{N-1}
Query_0
Query_1
Query_2
...
Query_{Q-1}

サンプル


入力1
5 4
1 10 100 10000 100000
3 2000
2 4
0 1000
3 2000
出力1
3
100000
4
入力2
10 10
79168129 221230408 251854510 288702776 392057367 468108804 659587257 693699391 829981104 925237945
2 0
0 478102319
2 5
3 240108555
3 100639673
2 4
3 805286844
2 2
0 211091526
0 771024367
出力2
79168129
468108804
2
1
392057367
9
251854510

提出


Go (1.14)