Problem: At Akabe High School, a programmer training school, there is a unique study session run by the students themselves. It is important for programmers to constantly adopt new technologies, so the aim of this activity is to develop the habit of self-study through this study session.

There are a total of N students, each with a score obtained as a result of the programming contest at the time of admission. At the study session, some of the N students will become leaders, and each leader will run their own group and join the group they run.

Students other than the leader cannot join a group run by a leader with a score lower than their own. In addition, one value r that is 0 or more is decided so that the difference between the scores of the students participating in the group and the leader is within r. That is, if the leader of a group has a score of s and your score is greater than or less than s --r, you will not be able to join the group.

You are the executive committee chair of the study session and decided to do a simulation to prepare for the operation. In the simulation, start with no leader and repeat the following operations several times.

* Add students as leaders.
* Remove the student from the leader.
* For the combination of leaders at the time of request, find the minimum r such that the number of students who cannot participate in any group is x or less.



Create a program that performs such a simulation.



input

The input consists of one dataset. The input is given in the following format.


N Q
s1
s2
::
sN
QUERY1
QUERY2
::
QUERYQ


The first line gives the number of students N (1 ≤ N ≤ 1000000) and the number of processing requests Q (0 ≤ Q ≤ 1000).

The following N lines are given the integer si (0 ≤ si ≤ 1,000,000,000) indicating the score of the i-th student. Students shall be numbered 1,2, ..., N.

The processing request QUERYi is given to the following Q line. Processing requests are given in chronological order. There are three types of processing requests: ADD, REMOVE, and CHECK, and each QUERYi is given in one of the following formats.


ADD a


Or


REMOVE a


Or


CHECK x


ADD a stands for adding a student with the number a (1 ≤ a ≤ N) to the leader.

REMOVE a represents removing the student with the number a (1 ≤ a ≤ N) from the leader.

CHECK x represents an output request. An upper limit on the number of students who cannot join any group x (0 ≤ x ≤ N) is given.

The input shall satisfy the following conditions.

* At any given time, the number of leaders will not exceed 100.
* Do not add students who are leaders at that time to leaders.
* Students who are not leaders at that time will not be removed from the leader.

output

At the time of each output request in chronological order, the minimum r is output on one line so that the number of students who cannot join any group is x or less. However, if it is impossible to reduce the number of people to x or less no matter what r is selected, NA is output.

Example

Input

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


Output

NA
2
1
0
0
0

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

const int INF = (int)1e9 + 1;

int main() {

    int n, q;
    cin >> n >> q;

    vector< pair<int,int> > tmp( n );
    for ( int i=0; i<n; ++i ) {
	cin >> tmp[i].first;
	tmp[i].second = i;
    }
    sort( tmp.begin(), tmp.end() );

    vector<int> s( n );//下からi番目のスコア: s[i]
    vector<int> f( n );//i番の人がスコア何番目か: f[i]
    for ( int i=0; i<n; ++i ) {
	s[i] = tmp[i].first;
	f[tmp[i].second] = i;
    }

    set<int> leader;//リーダーの番号
    while ( q-- ) {

        string op;
        int arg;
	cin >> op >> arg;

        if      ( op == "ADD" )    leader.insert( f[arg-1] );
        else if ( op == "REMOVE" ) leader.erase( f[arg-1] );
        else {//CHECK

            int fail_r = -1, succ_r = INF;//条件を満たさない最大のr と 満たす最小のr

            while ( succ_r - fail_r > 1 ) {
		
                int mid = (succ_r + fail_r)/2;//新しいr

                int count = 0; //リーダーによってカバーされる生徒の総数
		int prev = -1; //リーダーのうちスコアが一つ下の人のインデックス
                for ( int idx : leader ) {

		    //全スコア中でリーダーからr引いたスコアの人のインデクス
                    int l_idx = lower_bound( s.begin(), s.end(), s[idx]-mid ) - s.begin();

		    //全スコア中でリーダーのスコアのすぐ下の人のインデクス
                    int r_idx = upper_bound( s.begin(), s.end(), s[idx] ) - s.begin()-1;

                    if ( l_idx <= prev ) l_idx = prev + 1;//一つ下のリーダーの手前まで

                    count += r_idx - l_idx + 1;//カウントにリーダー自身を含める
		    
                    prev = r_idx;
                }

                if ( n - count <= arg ) succ_r = mid;
                else fail_r = mid;
            }

	    if ( succ_r == INF ) cout << "NA" << endl;
	    else cout << succ_r << endl;
        }

    }

    return 0;
}