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 "bits/stdc++.h"
// Custom Header {{{
#define ALL(x) x.begin(), x.end()
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}}

int N;
int score[1000100];
int p[1000100];
set<int> leaders;
unordered_map<int,int> lcnt;

void addLeader(int id) {
    const int offset = upper_bound(p, p+N, score[id]) - p - 1;
    const int leaderIdx = offset - lcnt[score[id]]++;
    leaders.insert(leaderIdx);
    return;
}

void removeLeader(int id) {
    const int offset = upper_bound(p, p+N, score[id]) - p - 1;
    const int leaderIdx = offset - (--lcnt[score[id]]);
    leaders.erase(leaderIdx);
    return;
}

void debug()
{
    for (int i = 0; i < N; ++i) {
        printf("%d ", p[i]);
    }
    printf("\n");
    printf("leaders : { ");
    for (int e : leaders) {
        printf("%d, ", e);
    }
    printf("}\n");
    printf("---------------------------------------\n");
}

int countHazure(int r)
{
    if (leaders.empty()) {
        return N;
    }

    vector<int> a;
    a.reserve(leaders.size());
    for (int idx : leaders) { a.push_back(idx); }

    const auto lb = [&](int v) { return lower_bound(p, p+N, v) - p; };

    int ans = N - a.back() - 1;
    ans += lb(p[a.front()] - r);

    for (int i = 1; i < a.size(); ++i) {
        ans += max<i64>(0, lb(p[a[i]] - r) - a[i-1] - 1);
    }

    return ans;
}

int solve(int X)
{
    i64 ng = -1;
    i64 ok = INF;

    while(ok - ng > 1) {
        i64 mid = (ok + ng) / 2;
        if (countHazure(mid) <= X) ok = mid;
        else ng = mid;
    }

    return ok;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int Q;

    cin >> N >> Q;
    for (int i = 0; i < N; ++i) {
        cin >> score[i];
        p[i] = score[i];
    }

    sort(p, p + N);
    for (int i = 0; i < N; ++i) {
        lcnt[p[i]] = 0;
    }

    while(Q--) {
        string com;
        int x;

        cin >> com >> x;
        if (com[0] == 'A') {
            --x;
            addLeader(x);
        }
        else if (com[0] == 'R') {
            --x;
            removeLeader(x);
        }
        else if (com[0] == 'C') {
            int ans = solve(x);
            if (ans >= INF) {
                cout << "NA" << "\n";
            } else {
                cout << ans << "\n";
            }
        }
        else if (com[0] == 'D') {
            cout << countHazure(x) << endl;
        }

        //debug();
    }

    return 0;
}

// vim: set foldmethod=marker :