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:
// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

//
struct BIT{
	int N;
	ll *bit;
	void init(int n){
		N=n;
		bit=new ll[N+1];
		rep(i,N+1)bit[i]=0;
	}
	ll sum(int i){
		ll s=0;
		while(i){
			s+=bit[i];
			i-=i&-i;
		}
		return s;
	}
	void add(int i,ll x){
		i++;
		while(i<=N){
			bit[i]+=x;
			i+=i&-i;
		}
	}
	void set(int i,ll x){
		ll pre=sum(i+1)-sum(i);
		add(i,x-pre);
	}
};
//

int N,Q,M;
int s[1000010];
int t[1000010];
multiset<int> lead;
multiset<int>::ite it;

vector<pi> merge(vector<pi> v){
	int n=sz(v);
	vector<pi> res;
	vector<pi> p;
	rep(i,n){
		p.pb(mp(v[i].fir,+1));
		p.pb(mp(v[i].sec,-1));
	}
	sort(p.begin(),p.end());
	int nest=0;
	rep(i,sz(p)){
		if(nest == 0){
			res.pb(mp(p[i].fir,-1));
		}
		nest += p[i].sec;
		if(nest == 0){
			res[sz(res)-1].sec = p[i].fir;
		}
	}
	return res;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	/*
	vector<pi> test;
	test.pb(mp(5,6));
	test.pb(mp(6,7));
	test.pb(mp(3,5));
	test.pb(mp(3,6));
	test=merge(test);
	rep(i,sz(test))cout<<test[i].fir<<" "<<test[i].sec<<endl;
	*/
	
	BIT B;
	B.init(1<<20);
	
	scanf("%d %d",&N,&Q);
	rep(i,N){
		scanf(" %d",s+i);
		t[i]=s[i];
	}
	
	sort(t,t+N);
	M = unique(t,t+N) - t;
	
	rep(i,N){
		int id = lower_bound(t,t+M,s[i])-t;
		B.add(id,1);
	}
	
	vector<pi> ranges;
	rep(_,Q){
		char c[8];
		int x;
		scanf(" %s %d",c,&x);
		if(c[0]=='A'){
			x--;
			lead.insert(s[x]);
		}
		if(c[0]=='R'){
			x--;
			lead.erase(lead.find(s[x]));
		}
		if(c[0]=='C'){
			int lo=-1,hi=INF;
			while(lo+1<hi){
				int mi=lo+hi>>1;
				
				ranges.clear();
				for(it=lead.begin();it!=lead.end();it++){
					ranges.pb(mp(*it-mi,*it+1));
				}
				//rep(i,sz(ranges))cout<<ranges[i].fir<<" "<<ranges[i].sec<<endl;
				ranges = merge(ranges);
				//rep(i,sz(ranges))cout<<ranges[i].fir<<" "<<ranges[i].sec<<endl;
				int sum=0;
				rep(i,sz(ranges)){
					int lb1 = lower_bound(t,t+M,ranges[i].sec)-t;
					int lb2 = lower_bound(t,t+M,ranges[i].fir)-t;
					sum += B.sum(lb1) - B.sum(lb2);
				}
				//if(hi-lo<5)cout<<mi<<": "<<sum<<endl;
				if(sum >= N-x) hi=mi;
				else lo=mi;
			}
			if(hi==INF)puts("NA");
			else printf("%d\n",hi);
		}
		//for(it=lead.begin();it!=lead.end();it++)cout<<*it<<" ";cout<<endl;
	}
}