Logo C++ Online Judge

C++

时间限制:15 s 空间限制:512 MB
TA:
Statistics

A room has n seats with distinct positive integer numbers. The numbers may have gaps. Initially, every seat is available.

Process the following commands in the order given:

  • BOOK x: reserve the available seat with the smallest number greater than or equal to x, and print its number. If there is no such seat, print -1 and leave the reservations unchanged.
  • FREE x: make seat x available again. This command prints nothing. The input guarantees that x is a currently reserved seat.

Input

The first line contains two integers n and q. The second line contains the n seat numbers in arbitrary order. The next q lines each contain one command.

  • 1 <= n, q <= 200000
  • Every seat number and command argument is between 1 and 1000000000.
  • A BOOK argument need not be a seat number.

Output

For each BOOK command, print the reserved seat number or -1 on its own line. Do not print anything for FREE commands.

Sample input

3 5
10 20 40
BOOK 15
BOOK 15
FREE 20
BOOK 15
BOOK 41

Sample output

20
40
20
-1

Library note

For an ascending std::set, the member function lower_bound(x) returns an iterator to the first element greater than or equal to x, or end() if no such element exists. Insertion, this member function, and erasure by key each take O(log m) time when the set contains m elements. You can also erase by iterator; averaged over a sequence of operations, this takes constant time per erasure.

You may use these operations without implementing a tree or proving their complexity. Any correct solution that meets the resource limits is accepted.