In a desolate forest at the edge of Potatoland, there is a fence seperating Potatolands from the outside world. All day long, many pigeons will visit the fence and sit there for a long period of time, up to days or even weeks. However, good times don't last, and all of a sudden, a hurricane has come and hit Potatoland!
The fence, being very weak, broke, and the remaning fence can only fit up to N pigeons! Oh no! Being the pigeon master, you must now control the usage of the fence for the pigeons. The pigeons have submitted to you their plans to use the fence. The plan consists of M events. Each event can either be:
- A 'LAND' event, which means a pigeon will land on the fence.
- A 'LEAVE' event, which means a pigeon will leave the fence.
- A 'EVACUATE' event, which means all the pigeons will leave the fence immediately.
Given a set of M
events, help the pigeons decide if the plan is alright by checking if at any point in time, the number of pigeons on the fence exceed the fence's maximum capacity. If so, output "PLAN REJECTED". If the number of pigeons on the fence will never exceed its maximum capacity, output "PLAN ACCEPTED". A LEAVE event will not be called if the fence is empty.
The first line of input will contain two integers, N and M.
The following M lines of input will contain one string, describing the event that occurs at that point in time, in chronological order.
Your output should contain one line with either "PLAN ACCEPTED" or "PLAN REJECTED".
Your output should terminate with a newline.
Subtask 1 (40%): 1 <= N, M <= 1 000
Subtask 2 (60%): 1 <= N, M <= 1 000 000
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2