C - Stołówka

Opis

Na pewnej uczelnianej stołówce żywią się zarówno studenci jak i pracownicy naukowi. Jak to zazwyczaj bywa w takiej sytuacji niektóre osoby są ważniejsze od innych. Na przykład gdy w kolejce stoją sami studenci i nagle przyjdzie pracownik, to on, jako najważniejszy, pierwszy zostanie dopuszczony do okienka z jedzeniem i pierwszy opuści kolejkę. Oczywiście pracownik pracownikowi nierówny - wszyscy magistrzy są mniej ważni od doktorów, a oni z kolei są mniej ważni od profesorów. Ważną rolę odgrywa jeszcze staż pracy, a w przypadku studentów rok studiów. Im ktoś dłużej pracuje/studiuje tym jest ważniejszy (oczywiście to tytuł jest elementem dominującym tak więc np. profesor z jednorocznym stażem jest ważniejszy niż doktor z 50-letnim stażem). W przypadku równej ważności o pierwszeństwie decyduje moment ustawienia się w kolejce.

Na stołówce podają każdego dnia zupę oraz drugie danie. Każde z nich jest podawane w osobnym okienku, do którego stoi osobna kolejka. Osoby, które chcą zjeść oba dania zaraz po wejściu do stołówki stają w kolejce po zupę, czekają na swoją kolej, odbierają zupę, siadają z nią przy stole, konsumują ją ileś czasu, zaraz po skończeniu zupy stają w kolejce po drugie danie, czekają na swoją kolej, odbierają drugie danie, konsumują, a skończywszy konsumpcję natychmiast opuszczają stołówkę. Czasem zdarzają się osoby, które chcą zjeść tylko zupę (wtedy zjadłszy ją od razu opuszczają stołówkę), albo tylko drugie danie (wtedy od razu stają w drugiej kolejce). Zdarza się też taka sytuacja, że stołówka kończy swoją działalność zanim wszystkie osoby skończą, czy nawet zaczną jeść. W takiej sytuacji wszyscy są bezwzględnie zmuszeni do opuszczenia stołówki. Nie zdarza się jednak tak, że ktoś przychodzi już po jej zamknięciu. Ruch osób na stołówce rządzi się następującymi prawami:

jeżeli kolejka nie jest pusta to co sekundę podchodzi do okienka najważniejsza osoba spośród czekających (a w przypadku osób o tej samej ważności - ta z nich, która ustawiła się najwcześniej), dostaje pożywienie i opuszcza kolejkę;
osoba, która właśnie weszła do kolejki może potencjalnie zostać obsłużona od razu - tak się dzieje na przykład w sytuacji gdy kolejka była pusta lub osoba wchodząca ma największą ważność;
jeżeli dwie lub więcej osób chce się ustawić w tej samej sekundzie, w tej samej kolejce to pierwsza ustawia się ta, która wcześniej pojawiła się na stołówce;
dla każdej pary osób da się określić, która z nich wcześniej pojawiła się na stołówce, nawet jeśli obie osoby przyszły w tej samej sekundzie (drzwi są zbyt wąskie, żeby obie osoby weszły dokładnie w tym samym momencie);
czasy przejścia między wejściem/wyjściem, kolejką i stołem są pomijalne (można przyjąć, że są równe 0), liczy się tylko czas stania w kolejce i czas jedzenia.

Zadanie

Dany jest czas otwarcia stołówki oraz lista osób, które kolejno się na niej pojawiały. Dla każdej z nich podane jest jej: tytuł (jeśli ma), imię, nazwisko, staż lub czas nauki, moment przyjścia na stołówkę (licząc od momentu jej otwarcia), czas jedzenia zupy (o ile chce jeść zupę) i czas jedzenia drugiego dania (o ile chce jeść drugie danie). Twój program powinien wypisać dla każdej osoby czas opuszczenia przez nią stołówki. Wszystkie czasy liczone są w sekundach.

Specyfikacja wejścia

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę dni, przez którą obserwujemy ruch na stołówce. Każdy z dni opisany jest następująco. W pierwszym wierszu znajdują się dwie liczby całkowite N i M oznaczające odpowiednio liczbę osób, które pojawią się na stołówce oraz czas przez jaki jest ona otwarta tego dnia (1 ≤ N ≤ 50.000, 1 ≤ M ≤ 1.000.000.000). W kolejnych N wierszach znajdują się osoby, które pojawiają się na stołówce (osoby są wymienione w kolejności przechodzenia przez drzwi), a każda z nich jest opisana przez następujące wartości (oddzielone od siebie pojedynczą spacją): Tytuł (opcjonalny), Imię, Nazwisko, R, Tw, Tz, Td. Tytuł może przyjmować jedną z trzech wartości: “mgr”, “dr” lub “prof.” (oznaczają one odpowiednio magistra, doktora i profesora). Brak tytułu oznacza, że osoba jest studentem. Imię i Nazwisko są ciągami liter alfabetu angielskiego o długości od 2 do 100. Pierwsza litera imienia i nazwiska jest zawsze duża, a pozostałe są małe. Jak to zazwyczaj w życiu bywa, mogą istnieć osoby o tych samych imionach i nazwiskach (czy nawet tytułach). Kolejne wartości w wierszu oznaczają odpowiednio: staż lub czas nauki (w pełnych latach), moment pojawienia się na stołówce, czas jedzenia zupy oraz czas jedzenia drugiego dania (czasy podane są w sekundach). Podlegają one następującym ograniczeniom: 0 ≤ R ≤ 50, 0 ≤ Tw ≤ M, 0 ≤ Tz ≤ 1.000.000.000, 0 ≤ Td ≤ 1.000.000.000. Uwaga, Tz=0 oznacza, że osoba nie chce jeść zupy, a Td=0, że drugiego dania (obie te wartości nie mogą być jednocześnie zerami).

Specyfikacja wyjścia

Dla każdego dnia opisanego na wejściu, należy wypisać N wierszy, w których mają się znaleźć kolejne osoby (tj. ich ewentualny tytuł oraz imię i nazwisko) z czasami ich wyjścia ze stołówki (podanymi w sekundach, licząc od momentu otwarcia). Osoby powinny pojawić się na wyjściu w takiej samej kolejności jak na wejściu.

Przykład

Wejście

2
3 100
dr Ccc Ddd 0 0 0 111
mgr Aa Bb 11 22 33 44
prof. Prof Prof 30 30 30 30
3 1000
Michal Kichal 1 10 15 20
prof. Huhu Ha 50 11 15 25
John Ixinski 1 25 0 22

Wyjście

dr Ccc Ddd 100
mgr Aa Bb 99
prof. Prof Prof 90
Michal Kichal 45
prof. Huhu Ha 51
John Ixinski 49

Wyjaśnienie

Pierwszy przykład jest trywialny. W drugim przykładzie Michal pojawia się w 10-tej sekundzie i od razu dostaje zupę, je ją przez 15 sekund, więc ustawia się w kolejce po drugie danie w 25-tej sekundzie. Dokładnie w tym samym czasie na stołówkę przychodzi John i również chce ustawić się w kolejce po drugie danie, ale pierwszeństwo ma Michal (jako że on pierwszy był na stołówce). Jak się okazuje jest to elementem decydującym gdyż obaj mają taką samą ważność, zatem Michal dostaje swoją porcję od razu. John musi odczekać sekundę, jednak dokładnie wtedy (tj. w 26-ej sekundzie) prof. Huhu Ha kończy swoją zupę i ustawia się w kolejce. Jako że jest on najważniejszy to pierwszy odbiera swoje danie. Dopiero w 27-ej sekundzie John dopchał się do okienka i dostał swój obiad. Moment opuszczenia lokalu już dalej można sobie łatwo wyliczyć.