勉強会

プログラマー養成校のアカベ高校には、生徒自身で運営するユニークな勉強会があります。プログラマーは新しい技術を常に取り入れることが大切なので、この勉強会を通して自学自習の習慣を身につけることがこの活動のねらいです。

生徒は全部でN人おり、それぞれが入学時のプログラミングコンテストの結果で得られたスコアを持っています。勉強会ではN人の生徒のうち何人かがリーダーになり、各リーダーがそれぞれのグループを運営するとともに、自らの運営するグループに参加します。

リーダー以外の生徒は、自分のスコアよりも低いスコアのリーダーが運営するグループには参加できません。また、0以上のある値rを１つ決め、グループに参加する生徒とリーダーのスコアの差がr以内となるようにしています。つまり、グループのリーダーのスコアがsのとき、自分のスコアがsを超えているか、あるいは s - r 未満ならば、そのグループには参加できません。

あなたは勉強会の実行委員長であり、運営準備のためにシミュレーションを行うことにしました。シミュレーションでは、リーダーが誰もいない状態から始め、以下の操作を何回か繰り返します。

• 生徒をリーダーに加える。
• 生徒をリーダーから外す。
• 要求時点でのリーダーの組み合わせについて、どのグループにも参加できない生徒がx人以下になるような、最小のrを求める。

このようなシミュレーションを行うプログラムを作成してください。

入力

入力は1つのデータセットからなる。入力は以下の形式で与えられる。

N Q
s1
s2
:
sN
QUERY1
QUERY2
:
QUERYQ

1行目に生徒の数N(1 ≤ N ≤ 1000000)、処理要求の数Q(0 ≤ Q ≤ 1000)が与えられる。

続くN行にi番目の生徒のスコアを示す整数s_i(0 ≤ s_i ≤ 1,000,000,000)が与えられる。生徒は1,2,...,N で番号付けされているものとする。

続くQ行に処理要求QUERY_iが与えられる。処理要求は時系列順に与えられる。処理要求はADD, REMOVE, CHECKの3種類あり、各QUERY_iは以下のいずれかの形式で与えられる。

ADD a

または

REMOVE a

または

CHECK x

ADD aは番号a(1 ≤ a ≤ N)の生徒をリーダーに加えることを表す。

REMOVE aは番号a(1 ≤ a ≤ N)の生徒をリーダーから外すことを表す。

CHECK xは出力要求を表す。どのグループにも参加できない生徒の数の上限x(0 ≤ x ≤ N)が与えられる。

なお、入力は以下の条件を満たすものとする。

• どの時点でも、リーダーの人数が100人を超えることはない。
• その時点でリーダーである生徒をリーダーに加えることはない。
• その時点でリーダーでない生徒をリーダーから外すことはない。

出力

時系列順に各出力要求の時点で、どのグループにも参加できない生徒がx人以下になるような最小のrを1行に出力する。ただし、どのようなrを選んでもx人以下にすることが不可能であればNAと出力する。

入力例 1

5 8
5
10
8
7
3
ADD 1
ADD 3
CHECK 0
CHECK 1
CHECK 2
CHECK 3
CHECK 4
CHECK 5

出力例 1

NA
2
1
0
0
0

入力例 2

5 28
5
10
8
7
3
CHECK 0
CHECK 1
CHECK 2
CHECK 3
CHECK 4
CHECK 5
ADD 1
CHECK 0
CHECK 1
CHECK 2
CHECK 3
CHECK 4
CHECK 5
REMOVE 1
ADD 3
CHECK 0
CHECK 1
CHECK 2
CHECK 3
CHECK 4
CHECK 5
ADD 1
CHECK 0
CHECK 1
CHECK 2
CHECK 3
CHECK 4
CHECK 5

出力例 2

NA
NA
NA
NA
NA
0
NA
NA
NA
2
0
0
NA
5
3
1
0
0
NA
2
1
0
0
0

---