is doing a contest. He comes across the following problem:

You have an array of elements. There are operations you need to perform on it.

Each operation is one of the following:

`I v`

Insert into the array.`R v`

Remove a single element from the array with a value of , if it exists.`S v`

Output the smallest element in the array. It is guaranteed that does not exceed the size of the array.`L v`

Output the index, starting from , of the first occurrence of in the array, if the array was sorted. Output if is not present in the array.

After all of the operations, print out all of the elements remaining in the array in non-decreasing order.

**To enforce performing operations in an online manner, will be encrypted.**

At any time, every element in the array is between and , inclusive.

per operation. He practices different data structures every day, but still somehow manages to get them wrong. Will you show him a working example?

knows that one fast solution uses a Binary Search Tree. However, he knows that a standard binary search tree has a worst case runtime of*Not a binary search tree.*

#### Input Specification

The first line has and .

The second line has integers, the original array.

The next lines each contain an operation in the format `C x`

, where is the type of operation. is encrypted: you should decode it by finding , where is the answer to the previous `S`

or `L`

operation (or if neither operation has occurred). You should perform the operation using . denotes the bitwise XOR operation.

#### Output Specification

For each `S`

or `L`

operation, output the answer on its own line.

After all operations have been finished, output all of the elements in the final array in non-decreasing order on a single line.

#### Sample Input

```
5 8
9 4 8 11 2
S 4
I 1
S 13
R 10
L 10
L -5
I 8
L 8
```

#### Sample Input (Not Encrypted)

For your convenience, here is a version of the sample input that is **NOT** encrypted. Remember, all of the real test files will be encrypted (like the input above).

```
5 8
9 4 8 11 2
S 4
I 8
S 4
R 2
L 2
L 4
I 9
L 9
```

#### Sample Output

```
9
8
-1
1
4
4 8 8 9 9 11
```

## Comments

You said it's welcomed to use map or policy based ds when i sumbited beside ac there is (cheater) and 0 points why ?

## Backstory:

A week after ZQFMGB12 uploaded the problem, bruce pointed out that this could be solved using policy-based data structures. So ZQFMGB12 tried to prevent people from using this.

A few weeks later, I managed to get in a submission that used policy-based data structures which avoided detection, rendering it moot.

## The Present

Fast-forward a year, and the checker still stands as a relic of the past. The challenge of using policy-based data structures is now in avoiding detection.

Hint: The detection system works by piping your code in through

`stdin`

to either a`gcc`

or`clang`

process, which has the flags`-E -DONLINE_JUDGE -xc++ -Wall -O2 -lm -march=native -s`

The picture says "not a binary search tree", but I checked it at least five times and I swear it's a binary search tree.

Although I'm also fairly sure that is a binary search tree. This problem requires more than a binary search tree to solve, for the select and rank queries, it needs an order statistic tree.

I don't understand how

(from the sample input) is equal to4 xor 1(from the decoded sample input). Can someone please explain?8It's xor the last answer, not the last input.

For some reason, I thought it meant the answer to the last xor operation, which was what confused me. Thanks for the clarification!

Can you use a map?

You are welcome to use anything, including this.

Is the first test the same as the sample?

This comment is hidden due to too much negative feedback. Click here to view it.