#P3306. Busy Airport

Busy Airport

Description

Today is a busy day of Mehrabad Airport. There are a lot of aircrafts requesting to land but unfortunately, the number of available bands for landing is a few. As a result, a policy has been set to manage the landing aircrafts:

  • Landing requests are processed in the order they are received.
  • While processing a landing request, if there is a free band, the band is allocated and the landing process starts immediately.
  • For each aircraft, the duration it takes, from the time its landing request is accepted to the time its landing is finished and the band is de-allocated, has been computed beforehand and is available now. Note that, if an aircraft starts landing at time 00:00:00.000 and it takes 10 minutes for it to land, then the band which was used for its landing is de-allocated at 00:10:00.000 and can be used by another aircraft at that time.
  • In the case there is no free band while processing a request, the request is temporarily rejected and the requesting aircraft is asked to request for landing again after 10 minutes.
  • In the case two aircrafts request to land at the same time, the request of the one with the smaller ID is processed first.

You are asked to write a program that, given the initial request time and the duration of landing for each aircraft, simulates the above process and generates a detailed report of in which order and at what times these aircrafts will land.

Input

The first line of input consists of a single integer T, the number of test-cases. Each test-case starts with a line containing two integers, , 1 ≤ R ≤ 100 , the number of aircrafts requesting to land and 1 ≤ B ≤ 10, the number of available bands for landing. Each of the next R lines contains the description of the landing aircraft consisting of the aircraft ID (less than 10000000), the date of arrival (due to Persian Calendar ) in the format 'dd/mm/yyyy' where 1178 ≤ yyyy < 1634 , the time of initial request for landing in the format 'hh:mm:ss.uuu' in 24 hour format, and the time-span 'hh:mm:ss.uuu', guaranteed to be at most 2 hours, which is the amount of time needed for that aircraft to land.

Output

For each test case, your program should first output a line containing the phrase 'Report for Test-Case #k:', where k is the index of the test-case, followed by the report associated with it. Each line of the report contains an entry which can be:

  • An accepted request: In this case, the entry contains the aircraft ID together with the date and time of the request followed by the word ACCEPTED.
  • A rejected request: In this case, the entry contains the aircraft ID together with the date and time of the request followed by the word POSTPONED.
  • A finished landing: is generated when an accepted aircraft is finished landing. It contains the aircraft ID together with the date and time of the request followed by the word LANDED.

The entries must be sorted in increasing order, according to the following conditions:

  • An entry with an earlier date should precede the other requests.
  • In the case of two entries with equal dates, the one with earlier time should precede the other
  • In the case some entries have equal dates and times, the finished landing entries should precede the others.
  • In the case none of the above rules are applicable between a pair of entries, the one with the lower ID precedes the other.

There should be an empty line after each test-case.

1
3 1
377 11/01/1385 10:45:54.000 00:04:00.000
367 11/01/1385 10:45:54.000 00:03:00.000
357 11/01/1385 10:48:54.000 00:04:00.000
Report for Test-Case #1:
367 11/01/1385 10:45:54.000 ACCEPTED
377 11/01/1385 10:45:54.000 POSTPONED
367 11/01/1385 10:48:54.000 LANDED
357 11/01/1385 10:48:54.000 ACCEPTED
357 11/01/1385 10:52:54.000 LANDED
377 11/01/1385 10:55:54.000 ACCEPTED
377 11/01/1385 10:59:54.000 LANDED

Hint

There may be situations in which handling of leap years is required. According to the Persian (Jalali) Calendar, leap year is a year which has 366 days instead of 365, and this extra day is added to the end of Esfand. You may assume that a given year is leap year if the remainder of it divided by 33 is either 1, 5, 9, 13, 17, 22, or 30. Actually, this formula is only correct if the given year is in the range [1178, 1634) but regardless of the given year in the input, use it for detection of leap years.

NOTE:It seems that there are 12 months in a Persian (Jalali) year. The first 6 month have 31 days. The following 5 months have 30 day. The last year has 29 or 30 days according whether or not it is leap year.

Source

Amirkabir University of Technology Local Contest 2006