You are given a bunch of data (all are positive 32 bit numbers) to operate on. The only operations on the data are search, insert, and delete. When storing the data you have to remember its rank, that is the original position when the data is being inserted. All successful operations must return the ranks of the data. Failed operations should return NONE as the answer.

Your objective is to execute all of the operations as fast as possible.

Input

The first line of input is N and M, separated by a space, N is the number of initial data. (0 <= N < 1000000) and M is the number of operations against the data. (0 <= M < 1000000).

The second line contains N data, separated by blanks. All data are positive 32 bits numbers

The next M lines contains operations against the data. Each line contains a symbol and a number, separated by a space. 

There are 3 symbols (S, I, D), each representing search, insert, and delete operation.

'S number' tries to find the number in the stored data, and outputs its first rank in the stored data (as originally inserted), or NONE if no such number exists.

'I number' inserts the number into the stored data, and outputs its rank in the stored data. (Data can be duplicated).

'D number' deletes the least ranked number found in the stored data, and outputs its rank, or NONE if no such number originally exists.

Output

There is an output for each executed operation. See the above input description about each operation for the detail of the output.

Example

Input:
10 6
20 12 10 28 20 50 49 8 51 1
S 20
I 3
S 11
D 20
I 2
S 20

Output:
1
11
NONE
1
12
5