SID - Search Insert Delete

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

Added by:Jimmy Tirtawangsa
Date:2012-10-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32-GCC C-CLANG C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 COBOL FORTRAN GO GOSU JAVA JULIA KTLN LUA OBJC OBJC-CLANG PAS-GPC PAS-FPC PYTHON PYPY PYPY3 PYTHON3 RUST
Resource:Own problem

hide comments
2012-10-31 14:29:53 Problem Solver
is it expected to do it in O(N+M)?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.