14910 - Spider-Man's Taxi Service   

Status  |  Limits Submit

Description

After the success of Spider-Man's queue service, Spider-Man decided to build a taxi service suited for the citizens of New York City.

The service need to support adding available drivers to the queueing system and provide immediate services to the riders. However, in order to please the shareholders, Spider-Man needs to add a subscription service for both drivers and riders. This status gives them golden status, making the system always prioritize serving their requests.

Commands:

  • addDriver <Driver_id>: Add regular driver with id <Driver_id> to the driver queue
  • addGoldenDriver <Driver_id>: Add golden driver with <Driver_id> to the driver queue
  • addRider <Rider_id>: Add regular rider with id <Rider_id> to the rider queue
  • addGoldenRider <Rider_id>: Add golden rider with id <Rider_id> to the rider queue
  • dispatch: Assign a driver in the driver queue to a rider in the rider queue​​

Rules for dispatch:

  1. Golden drivers/riders have higher priority than Regular driver/riders
  2. With multiple drivers/riders in the same prioirity, choose the earliest one that entered the queue
  3. Return assigned driver id and rider id in (<Rider_id>, <Driver_id>)
  4. If no available driver/rider, return (-1,-1)

Input

First line is an integer N indicating the number of commands.

Following N lines are one of the five commands mentioned above.

All <Driver_id> are unique integers.

All <Rider_id> are unique integers.

1<=N<=100000

1 <= <Driver_id>/<Rider_id> <= 100000

First testcase is similar to sample I/O.

3 of the testcases will not use addGoldenDriver and addGoldenRider command

Output

Everytime when dispatch command is called, output the pair (<Rider_id>, <Driver_id>) and '\n'.

If no availabe driver/rider, return (-1, -1)

No need to output anything for other commands.

Sample Input  Download

Sample Output  Download

Tags




Discuss