C Programming Language

Problem Title: Introduction to Database

Database is a structurized method for data storage and perform operations related to the data. There are Some simple operations that can be done by a database are Insert, Alter, Delete, and Query. There are N different integers stored. You are asked to create a database where you can carry out the following 4 operations : 1. I X - this operation is insert operation, inserting X to the database. 2. A X Y - Alter operation that alter data with value of X to Y . 3. D X - this operation is to delete X-valued data from the database. 4. Q X - Query operation, to count number of data that less than or equal to X. It is also guaranteed that : 1. Insert will add data that is not exist in the database. 2. Alter operation will change data in the database to a new data that is not exist in the database. 3. Delete operation will delete data from the database. The value that want to be deleted always exist. 4. At most 250 operations for Insert, Alter, and Delete.

Format Input

Input consists of two integers N and K - number of data and number of operation. The next line contains N integers as the initial data stored in the database. Then followed by K lines each contains an operation command (I, A, D, or Q) and followed by an integer X for operation I, D, Q or two integers X and Y for A operation.

Format Output

For each Q operation, output an integer that shows number of data that does not exceed the query.

Constraints

1 N 100000 1 K 10000 0 X , Y 1000000000

Sample Input & Output (standard input & output)

6 7

2 3 4 5 6 7

Q 4

Case #1: 3

I 1

Q 4

Case #2: 4

D 2

Q 4

Case #3: 3

A 6 2

Q 4

Case #4: 4