judgequeue

Problem Description

While coding the OJ judge system last year, Rar the Cat has encountered a problem with coding the judge queue and needs your help.

In this hypothetical scenario, there will be up to N submissions in total, each with a unique submission id (subID).

However, each submission should be in the queue with a different priority. Rar the Cat thus wants 4 ways to add a submission to the queue.

The 4 ways are:

1. void push_front (int subID) : Queue a submission of subID to the front of the queue
2. void push_back (int subID) : Queue a submission of subID to the back of the queue
3. void insert_before (int subID, int ref) : Queue a submission of subID before the submission with subID of 'ref'
4. void insert_after (int subID, int ref) : Queue a submission of subID after the submission with subID of 'ref'

Furthermore, there are also 4 ways for the judge to inspect or access the queue.

The 4 ways are:

1. int queue_front () : Returns the subID of the submission at the front of the queue
2. int queue_back () : Returns the subID of the submission at the back of the queue
3. int sub_before (int ref) : Returns the subID of the submission just before the submission with subID of 'ref'
4. int sub_after (int ref) : Returns the subID of the submission just after the submission with subID of 'ref'

In addition, the judge also needs to update the queue when a submission has been graded. There are 3 ways for the judge to update the queue:

1. void pop_front() : Deletes the first submission of the queue
2. void pop_back() : Deletes the last submission of the queue
3. void erase (int subID) : Delete the submission with 'subID' from the queue

It's now your job to implement all these functions!

Furthermore, an initialize function (void init(int X, int N) ) will also be called before any of the above functions are called. You can put any initialization code here.

Implementation

This is a function call question, there is a template provided under Attachments. Please use that template, you do not need to declare int main() or input from file.

For testing purposes, you may uncomment the int main() from the template. Please remember to comment it back when submitting the problem.

Limits

Unless otherwise specified, 0 < N ≤ 1000000 for each testcase, this means that subID can range from 1 to N

X will be the maximum number of function calls for each testcase. The limits of X will be addressed in the subtask section.

It is guaranteed that the system will not attempt to add any submissions that are already in the queue into the queue again. However, a submission can be requeued after it has been deleted from the queue previously.

Subtasks

Subtask 1 (33%): X ≤ 10,000,000, There will only be the following functions: queue_front, push_back, pop_front

Subtask 2 (31%): X ≤ 10,000,000 There will not be the following functions: insert_before, insert_after, erase.

Subtask 3 (36%): X ≤ 10,000,000

Subtask 4 (0%): Sample Testcase

Input

The first line of input (for your grader) will consist of 2 integers, X followed by N, where N is the maximum of all the subIDs in the problem.

Sample Input

12 5
push_back 1
push_back 2
push_front 3
sub_before 1
sub_after 1
insert_after 4 1
insert_before 5 4
pop_front
pop_back
erase 4
queue_front
queue_back

Sample Output

3
2
1
5