The era of technology is so hectic at times! Each & every single day, the crying needs for faster & faster processors are becoming more important than before with the continuously increasing complexity of applications & tasks. One of the solutions that the processor manufacturers are successfully employing nowadays is parallel processing. Scheduling of tasks is a prime concern while designing faster processors having several components working in parallel. We are currently building a new microprocessor that has P logical sub-processors in it. Each of the logical sub-processors can act as an individual processor & process one of the available tasks during a time slot. Note that, a logical sub-processor can process only a single task in one time slot & a task can not be processed by more than one processor during a time slot. Now, you are given the arrival time (the time when a task becomes available to the processors), processing time (the number of time slots necessary to complete processing the task) & deadline (the earliest time when the processing of this task is required to be completed) for T tasks. You have to figure out if it is possible to schedule the tasks using the available resources in such a way that all tasks are completed before their respective deadlines. Let us be a bit more specific. From now on we shall assume, each time slot equals 1 micro-second. The span of the first time slot is 0 to 1 micro-second while the second time slot is 1 to 2 micro-second & so on. For example, consider a multi-processor system with 2 logical sub-processors. You are needed to schedule 3 tasks A, B & C with the following data. Task Arrival Time Processing Time Deadline A022 B034 C123 It is possible to schedule these 3 tasks in the given system so that all the tasks meet their respective deadlines i.e. processing of task A, B & C are completed at (or before) time 2 micro-second, 4 micro- second and 3 micro-second respectively. Look at the following table for a possible schedule. Time Available Assigned to Assigned to Completed Due (micro-second) tasks processor -1 processor -2 tasks tasks 0 A,B A B - - 1 A,B,C A C - - 2 B,C B C A A 3 B B - A,C A,C 4 - - - A,C,BA,C,B Input The first line of the input is the number of test cases C (1 ≤ C ≤ 50). C test cases follow. A test case begins with 2 integers P (1 ≤ P ≤ 40) and T (1 ≤ T ≤ 40), as described earlier. Each of the next T lines gives a task detail. A task detail consists of 3 integers — arrival time, Ai (0 ≤ Ai ≤ 1000), processing time, Ri (1 ≤ Ri ≤ 5000) and deadline, Di(Ai + Ri ≤ Di ≤ 10000). Output For each test case, print ‘FEASIBLE’ in a line if there is a possible schedule to meet all the deadlines. Otherwise, print ‘NO WAY’.
2/2 Sample Input 2 23 022 034 123 23 022 033 123 Sample Output FEASIBLE NO WAY