Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Device ID

Limits 1s, 512 MB

A device ID is a distinct number associated with a smartphone or similar handheld device. Every smartphone has a unique device ID.

Now, you have got a job in CodeMask Mobile Company & your task is to set device IDs for new made handsets. You have to select unique device ID for handsets. But the company maintains a rule. You can also recycle some device IDs. That means, if some devices are destroyed, you can use those devices in the future.

So, you have to do three kinds of works:

  1. Assign value x to a new made handset.
  2. Delete value x from the device ID list because the handset having this device ID is destroyed.
  3. Answer what is the first free device ID still now. For example. If the values 3, 6, 9 are used as device IDs, then the first free device ID is 1, because it is not used. If the values 1,2,5,10 are used as device IDs, then the first free device ID is 3.

Now as an employee of CodeMask Mobile Company, you have to do these three tasks.

Input

The input file contains several test cases T (T <= 5).

In every test case, the first line contains a value N (number of tasks to complete, 1 <= N <= 100000).

Then next N lines contains one of the following lines:

  • 1 x (type 1 task, x is the new value to add)
  • 2 x (type 2 task, x is the old value to destroy)
  • 3 (ask for the first free device ID)

(1 <= x <= 1000000000)

Output

For each test case, the first line should be the line with case number as “Case y:” where y is the case number. After that each line contains a number for the 3rd type of task.

Sample

InputOutput
1
6
1 3
3
1 1
3
2 1
3
Case 1:
1
2
1

This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.

Discussion

Statistics


83% Solution Ratio

aminulEarliest, May '16

RobbinFastest, 0.1s

khepa98Lightest, 786 kB

emrul_muShortest, 704B

Submit

Login to submit