Training Site
Sideways banner

Unofficial Contestants

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 120 megabytes
Time limit: 2.0 seconds

You are this year's director for the NZIC (Nutritious Zucchini Ingesting Contest). You might already know that in NZIC there are two types of contestants - official and Austrunofficial contestants. Only official contestants are ranked on the scoreboard. However, NZIC has been growing rapidly in the past years. For some reason, there's been a sudden influx of unofficial contestants in the past year or two. NZIC needs a faster algorithm to handle all of these new contestants.
There are N competitors in the NZIC, numbered from 1 to N. The contest has already ended, and the competitors are numbered in terms of their rank. In other words, competitor number 1 has ingested the largest number of nutritious zucchinis and is in first place, competitor number 2 is in second place, competitor number N is in last place, and so on. All of the contestants are initially official contestants.
However, the NZIC allows competitors to toggle their status after the contest has ended. Toggling changes an official status to an unofficial status, and vice versa. A competitor can toggle their status any number of times - for example, if they toggle their status twice, they change from official to unofficial, then back to official.
You will be given a list of M queries. Each query will either ask you to toggle the status of a competitor, or to output the official rank of a competitor.


The first line contains N, the number of competitors.
The second line contains M, the number of queries.
M lines will follow.

  • P of these will contain the character 't', followed by a number i. This means you must toggle the status of the i-th competitor.
  • Q of these will contain the character 'o', followed by a number j.


For each line containing the character 'o', output the official rank of competitor number j. If competitor j is an unofficial competitor, output 'UNOFFICIAL' instead. You do not have to output each rank immediately after reading the line - if you wish, you can start to output after reading in all the input.


  • 1 \le N \le 1,000,000,000
  • 1 \le M \le 50,000
  • P + Q = M
  • Q >= 1
  • 1 \le i, j \le N for all queries


  • Subtask 1 (+25%): 1 \le N \le 1,000 and 1 \le M \le 500.
  • Subtask 2 (+20%): N \le 100,000. Additionally, j = 50,000 for all output queries - we only ever ask for the rank of competitor number 50,000.
  • Subtask 3 (+15%): N \le 100,000. Additionally, 50,000 \le j \le 50,050 for all output queries.
  • Subtask 4 (+37%): 1 \le M \le 500.
  • Subtask 5 (+3%): No further constraints apply.

Note: Subtask 5 is an 'extra for experts' subtask, so you may want to start working on the next problem first.

  • Sample Input 1

    o 1

    Sample Output 1

  • Sample Input 2

    t 1
    o 1

    Sample Output 2

  • Sample Input 3

    t 2
    o 1
    o 3
    o 4

    Sample Output 3