Meteory

Limit pamięci: 64 MB

Bajtocka Unia Międzygwiezdna (BUM) odkryła niedawno w pobliskiej galaktyce nową, wyjątkowo interesującą planetę. Co prawda nie nadaje się ona do kolonizacji, lecz co jakiś czas nawiedzają ją deszcze nietypowych, nieznanych wcześniej meteorów.

Państwa członkowskie BUM umieściły tuż przy orbicie nowo odkrytej planety stacje badawcze, których głównym zadaniem jest zbieranie próbek przelatujących skał. Komisja BUM podzieliła orbitę na sektorów ponumerowanych kolejno od do , przy czym sektor sąsiaduje z sektorem . W każdym sektorze znajduje się dokładnie jedna stacja badawcza, należąca do jednego z państw członkowskich BUM.

Każde państwo wyznaczyło liczbę próbek meteorów, jakie pragnie zebrać przed zakończeniem misji. Twoim zadaniem jest, na podstawie prognozy deszczów meteorów na najbliższe lata, wyznaczyć dla każdego państwa, kiedy będzie mogło zakończyć badania.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę państw członkowskich BUM oraz liczbę sektorów, na jakie podzielona została orbita.

W drugim wierszu znajduje się liczb całkowitych (), pooddzielanych pojedynczymi odstępami i oznaczających państwa będące właścicielami poszczególnych sektorów.

W trzecim wierszu znajduje się liczb całkowitych (), pooddzielanych pojedynczymi odstępami i oznaczających liczby próbek meteorów, jakich poszczególne państwa potrzebują do zakończenia badań.

W czwartym wierszu znajduje się jedna liczba całkowita () oznaczająca liczbę przewidywanych opadów. W kolejnych wierszach znajdują się opisy deszczów meteorów w kolejności chronologicznej. W -tym z tych wierszy znajdują się trzy liczby , , (pooddzielane pojedynczymi odstępami), oznaczające, że w sektorach (jeśli ) lub sektorach (jeśli ) wystąpi deszcz meteorów, w wyniku którego wszystkie znajdujące się tam stacje badawcze uzyskają po próbek skalnych ().

W testach wartych przynajmniej 20% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. W -tym wierszu powinna znaleźć się liczba całkowita , oznaczająca numer deszczu, po którym stacje badawcze -tego państwa zgromadzą łącznie co najmniej próbek skalnych, lub słowo NIE, jeśli dane państwo nie będzie mogło skończyć badań w przewidywalnej przyszłości.

Przykład

Dla danych wejściowych:

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

poprawną odpowiedzią jest:

3
NIE
1

Autorzy zadania: Paweł Mechliński i Jakub Pachocki.