Aquapark
Limit pamięci: 64 MB
Nowy dyrektor Bajtockiego Aquaparku zbiera informacje o swoich pracownikach.
Chce sprawdzić, którzy ratownicy są najbardziej pracowici, a którzy z nich
lenią się podczas pracy.
Pracowitość ratownika jest ściśle zależna od liczby dzieci, których pilnuje,
ponieważ bardziej pracowici ratownicy wybierają miejsca, w których kąpie się
wiele dzieci, natomiast leniwi stronią od nich.
Cały Aquapark ma kształt kwadratu o boku długości i jest podzielony na segmentów
w kształcie kwadratu o boku długości 1.
Każdy z segmentów może być albo basenikiem, albo alejką między basenikami.
W każdym baseniku kąpie się pewna liczba dzieci.
W Aquaparku rozmieszczonych jest punktów, w których znajdują się ratownicy.
Ratownik, według najnowszych zasad bezpieczeństwa, może poruszać się jedynie równolegle do ścian Aquaparku,
bez względu na to, czy porusza się po alejkach, czy płynie w baseniku.
Stąd odległość, jaką przebędzie między dwoma punktami , ,
wynosi zawsze .
Każdy ratownik ma określony obszar, który musi chronić.
Dla -tego ratownika są to wszystkie baseniki położone w odległości nie większej niż od jego
pozycji początkowej.
Chcielibyśmy poznać pracowitość każdego ratownika.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite
oraz (, ),
oddzielone pojedynczym odstępem i oznaczające odpowiednio długość boku Aquaparku
oraz liczbę ratowników.
W następnych wierszach znajduje się mapa Aquaparku.
W -tym spośród nich znajduje się opis -tego rzędu segmentów aquaparku,
składający się z liczb całkowitych nieujemnych
(), pooddzielanych pojedynczymi odstępami.
Jeżeli liczba jest zerem, to znaczy, że segment o współrzędnych
(, ) jest alejką. Jeżeli natomiast jest ona dodatnia, to oznacza, że
segment ten jest basenikiem, w którym kąpie się dzieci.
W każdym z następnych wierszy znajduje się opis jednego ratownika.
Opis ten składa się z trzech liczb całkowitych
, oraz (, ),
pooddzielanych pojedynczymi odstępami,
oznaczających odpowiednio współrzędne (wiersz, kolumna) miejsca -tego
ratownika oraz maksymalną odległość chronionych przez niego baseników.
Możesz założyć, że w 50% przypadków testowych każdy basenik
jest chroniony przez co najwyżej jednego ratownika.
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie
wierszy.
W -tym wierszu powinna znaleźć się dokładnie jedna liczba całkowita
oznaczająca liczbę dzieci pilnowanych przez -tego ratownika.
Przykład
Dla danych wejściowych:
5 2
6 3 0 0 9
7 1 4 0 5
0 5 0 0 2
0 0 0 8 0
1 2 0 0 0
2 2 1
4 5 2
poprawną odpowiedzią jest:
20
15
Autorzy zadania: Joanna Bujnowska, Jacek Tomasiewicz.