JobScheduler

A job scheduler to schedule M jobs on N threads on a single machine. The input contains the following data:

1. Job Name
2. Duration: time taken for job completion
3. Priority: priority of the job. P0>P1>P2
4. Deadline: Expiry time after which job should not be run (The clock starts from 0 and deadline is the actual clock time)
5. UserType: Type of user who has initiated the job, Precedence of users Root>Admin>User

There are various scheduling algorithms-

Shortest Job First - SJF

Shortes job first (SJF), is a scheduling policy that selects the waiting process with the smallest execution time to execute next. In case of tie choose the job according to the following order-

1. Priority(higher priority job gets scheduled first)

First Come First Serve -FCFS

Jobs are executed on first come,first serve basis. Take the input as the order of jobs need to be scheduled.

Fixed Priority Scheduling -FPS

Each process is assigned a priority. Process with highest priority is to be executed first and so on. In case of tie choose the job according to the following order-

1. User Type
2. Longest Job First

Earliest Deadline First - EDF

Next job will be searched on the basis of job which is closest to its deadline. In case of tie, choose the job according to the following order-

1. Priority(higher priority job gets scheduled first)
2. Duration(lesser duration job gets scheduled first) In case we cannot schedule a job such that it completes before its deadline then it should be ignored.

You would be given a list of jobs (refer example below for format) and number of threads as input. You are expected to print the order of jobs scheduled for each algorithm on each thread as output.

Example

Input

Threads= 2

Job Name	Duration	Priority	Deadline	User Type
J1	10	P0	10	Root
J2	20	P0	40	Admin
J3	15	P2	40	Root
J4	30	P1	40	User
J5	10	P2	30	User

Output

SJF
Thread 1 - J1, J3, J4
Thread 2 - J5, J2

FCFS
Thread 1 - J1, J3, J5
Thread 2 - J2, J4

FPS
Thread 1 - J1, J4, J5
Thread 2 - J2, J3

EDF
Thread 1 - J1, J2
Thread 3 - J5, J4