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.