An airport is a location where aircraft such as fixed-wing
aircraft, helicopters, and blimps take off and land. Aircraft may be stored or
maintained at an airport.
Squeaky International Airport (SIA) is one of the busiest
airports in the world. As such, its
berths are usually filled, and due to limited supply, the airport tax for
landing at the airport is pretty high.
Like any other profit-driven corporation, the aim of SIA is to maximise
the taxes that it can collect from the aircraft.
The tax is very simple to calculate - it is simply
$1000 per aircraft, no matter how big or how long it berths at the airport.
It is reaching the Christmas season, and submissions of
application for landing at the airport has quadrupled.
As SIA's hired flight schedule manager, you are tasked to
approve or reject each application, in order for SIA to collect the most taxes,
but yet have enough berths for all the aircrafts at all times.
You may assume that landing and taking off do not take any
The same berth can be used for a flight which takes off at
the same time as a flight that lands.
The first line contains two integers, N
(1 ≤ N ≤ 1000000), the number of applications, and B (1 ≤ B ≤ 1000000),
the number of berths in the airport.
The next N lines contain the applications (in no particular
order). Each of these lines contain two
integers, Li and Ti (0 ≤ Li < Ti ≤ 232 − 1), the time that the aircraft
lands and takes off respectively.
Output N lines, each line containing a string either
"APPROVED" or "REJECTED" stating if the application has been approved or
rejected, in the same order as given in the input.
There might be more than one solution and all such solutions will be accepted.
Subtask 1 (0 points): Sample
Subtask 2 (10 points): 1 ≤ N ≤ 20; B = 1
Subtask 3 (30 points): B = 1
Subtask 4 (60 points): No constraints