***IN C PROGRAMMING LANGUAGE***

***DO NOT USE C++***

For this problem you will try to emulate some basic functions of a Task Manager. You must support the addition and removal of tasks. Each task will be assigned a priority as a non-negative integer (1,000,000,000=highest, 0=lowest). No two distinctly named tasks will have the same priority. Additionally for a given run you can assume that each task with the same name will have the same priority.

Your Task Manager must support two types of operations. Type 1 is the creation of a new task.

Type 2 is to determine the name of a task with a particular priority.

Input Specification

The first line of input contains a single positive integer n (n ? 10,000,000), which represents the total number of queries and addition deletions combined. Each of the following n lines begins with a single integer; the i-th lines integer describes the i-th operation type.

- When the beginning integer is 1 the operation is an add task operation. The remaining line will contain a task name followed by the tasks priority.

- Then the beginning integer is 2 the operation is the query operation. The remaining line will contain a single integer representing the desired task names priority.

- It is guaranteed that each location will be visited before Stackulas stack is permanently emptied (after visiting the first location).

- The name of each task will be composed strictly of at most 19 upper and lowercase Latin letters.

Output Specification

For each attempted task addition you will output a single line containing either ADDED, which means the task was not already present in the task list and was successfully added, or REDUNDANT which means that task was already in the list and therefore not added to the Task Manager.

For each name query operation you will output a single line containing either the associated name with the task or the string NON-EXISTANT, which means the task was not in the Task Manager.

Explanations

Case 1

Note in the above pictorial example. We sort the tasks in the Binary Search Tree for this problem by their priority (not their name). Every Program added is unique except for the last one (the second E for the tenth input operation).

Regarding the program name by priority

The 11-th operation asks for the name of the task with priority 3. The task with priority 3 is C.

The 12-th operation asks for the name of the task with priority 5. The task with priority 5 is E.

For the 13-th operation, which asks for the task with priority 10. Our tree should find that there is no task with priority 10. Due to this we print NON-EXISTANT.

For the 14-th operation we find that D has priority 4.

The 11-th operation asks again for the name of the task with priority 3. Again the task with priority 3 is C.

Case 2

There are five unique programs added,

- ProgramOne (operation 1 priority 1)

- BoiledWater (operation 2 priority 2)

- ColdFerret (operation 3 priority 3)

- MoonsShadow (operation 6 priority7)

- ThatOtherProgram (operation 7 priority 6)

For the following 6 name query operations we observe that,

- ColdFerret has priority 3.

- Nothing has priority 5.

- Nothing has priority 10.

- Nothing has priority 4.

- ColdFerrt has priority 3.

- BoiledWater has priority 2.

Case 3

Note that although later in the case ProgramTwo and ProgramThree are added, the first time their priorities are queried they dont exist yet. For this reason the third and fourth line are

NON-EXISTANT. Additionally by the eighth query ProgramThree has not been added, so it also results in NON-EXISTANT.

Grading Information

Reading from standard input 5 points

Writing to standard output 5 points

Comments, white space usage, and reasonable variable names 10 points

No output aside from the answer (e.g. no input prompts) 10 points

Uses strings (char arrays) for the task names 10 points

Implements Linked Binary Search Tree data structure 10 points

Your program will be tested on 10 test cases 5 points each

Five cases will have less than or equal 1000 simultaneous tasks at any given time No points will be awarded to programs that do not compile.

Solutions that dont try to implement a linked binary search tree will receive a maximum of 50 points

Only cases that finish within the maximum of {5 times the judge solution, 10 seconds} will be graded.

To get Full credit you will likely need to implement a balancing Binary Search Tree. The two methods that will be (or have been) covered in class are Red-Black Trees and AVL Trees.

Input Output Example Input 15 1 F 9 1 A 1 1 I 7 1 H 8 1 D 4 1 C3 1 E 5 1 B 2 1 J 6 1 E 5 2 3 2 5 2 10 Output ADDED ADDED ADDED ADDED ADDED ADDED ADDED ADDED ADDED REDUNDANT NON-EXISTANT 2 3 13 1 ProgramOne 1 1 BoiledWater 2 1 ColdFerret 3 1 ProgramOne 1 1 ProgramOne 1 1 MoonsShadow 7 1 ThatOtherProgram 6 ColdFerret 2 3 2 5 2 10 ADDED ADDED ADDED REDUNDANT REDUNDANT ADDED ADDED NON-EXISTANT NON-EXISTANT NON-EXISTANT ColdFerret BoiledWater 2 3 12 1 ProgramOne 1 2 1 ADDED ProgramOne NON-EXISTANT NON-EXISTANT ADDED ProgramOne ProgramTwo NON-EXISTANT ADDED ProgramOne ProgramTwo ProgramThree 2 100 1 ProgramTwo 2 2 1 2 100 1 ProgramThree 100 2 1 2 100