長さ の整数配列 が与えられる。
連続部分配列の座標圧縮を次のように定義する。その部分配列に現れる異なる値の個数を とする。部分配列内の各値 を、同じ部分配列に現れる異なる値のうち より小さい値の個数に置き換える。圧縮後の値は 以上 以下となる。部分配列の外側の要素は変化しない。
以下の 種類のクエリを順に処理せよ。
1 : 区間 を座標圧縮する。2 : 区間 の最小値を 、最大値を とする。この区間に実際に存在する値のうち、 に最も近い値を出力する。複数の異なる値が同じ距離にある場合は、最も小さい値を出力する。各クエリは、それ以前のすべてのクエリが適用された後の配列に対して実行する。
入力は次の形式で与えられる。
種類 2 の各クエリについて、条件を満たす値を 行に つずつ出力する。
最初の種類 1 のクエリの後、配列は となる。2 回目の後は となる。
3 : 区間 のすべての要素に整数 を加える。各クエリは次の つの形式のいずれかで、 行に つずつ与えられる。
3 のクエリでは 。1 のクエリは全体で高々 回である。追加の制約はない。
最初の二つのクエリでは、中点からの距離が等しい二つの値のうち、小さい方を出力する。