Problem B
Indexed Min Priority Queue

An indexed priority queue is one where your heap consists of indices; for instance, we can have a priority queue of objects, where what you get when you peek or poll is simply the index (id) of the object, and not the actual object itself. In order to know how the indices are sorted on the heap, each index is associated with a comparable key (priority). The great benefit of this data structure is that it allows us to remove an object or change its key in logarithmic time, if we know its index.

Input

On the first line, two integers $m$ ($1 \leq m \leq 100\, 000$) the number of indices the priority queue need to accommodate, and $q$ ($1 \leq q \leq 100\, 000$) the number of queries. Then follows $q$ lines, the $i$’th of which begins with a character $c_ i$ ($c_ i \in \{ \texttt{A}, \texttt{C}, \texttt{E}, \texttt{G}, \texttt{P}, \texttt{R}, \texttt{S}\} $). Depending on $c_ i$, the line may contain more tokens.

• A (add) - two integers $x_ i$ and $k_ i$ follows on the same line, indicating that the index $x_ i$ is added to the priority queue with key $k_ i$. If the index is already assigned, print error on the next line and do not process any of the later queries; otherwise, do not print anything for this query.

• C (change) - two integers $x_ i$ and $k_ i$ follows on the same line, indicating that the index $x_ i$ changes key to $k_ i$. If the index is not already assigned, print error on the next line and do not process any of the later queries; otherwise, do not print anything for this query

• E (peek) - no further tokens follow on this line. If the priority queue is empty, print error on the next line and do not process any of the later queries; otherwise, print the index with the lowest key.

• G (getKey) - an integer $x_ i$ follows on the same line, indicating that you should print the key assigned to index $x_ i$. If $x_ i$ is not in the priority queue, print error on the next line and do not process any of the later queries; otherwise print the key given to $x_ i$ in the priority queue.

• P (poll) - no further tokens follows on this line. If the priority queue is empty, print error on the next line of the output and do not process any of the later queries; otherwise, print the index with the lowest key, and then remove it from the priority queue.

• R (remove) - an integer $x_ i$ follows on the same line, indicating that the index $x_ i$ should be removed from the priority queue. If $x_ i$ is not in the priority queue, print error on the next line and do not process any of the later queries; otherwise do not print anything for this query.

• S (size) - no further tokens follow on this line. Print on the next line the current size of the priority queue.

For every integer $x_ i$, it holds that $0 \leq x_ i < m$, and for every integer $k_ i$ it holds that $-2^{31} \leq k_ i \le 2^{31}$. You may assume that all priorities are distinct, i.e. $k_ i = k_ j$ implies $i = j$. Note that both the input and output can be huge - consider using fast input and output methods.

Output

For each query, output a line according to the specifications given above.

3 11
A 0 300
A 1 100
A 2 200
S
G 0
R 1
R 0
S
G 2
R 0
S

3
300
1
200
error

3 8
A 0 300
A 1 100
A 2 200
E
P
P
P
P

1
1
2
0
error

3 15
A 0 300
A 1 100
A 2 200
C 0 50
E
C 2 40
E
C 0 400
C 1 500
C 2 600
C 0 700
C 1 800
P
P
P

0
2
2
0
1