Archiwum zadań programistycznych WWSI

Jan jest szczęściarzem, odkrył on na swojej działce złoża wody źródlanej oraz mineralnej. Nasz bohater postanowił to wykorzystać i wykonał po 101 odwiertów w 101 rzędach, a następnie zamontował w nich urządzenia do wydobywania wody. Pomiędzy maszynami ułożył tory, po których przemieszcza się kolejka ze zbiornikiem, do którego nalewana jest woda. Zebrana woda jest przelewana ze zbiornika do butelek dopiero po zakończeniu wydobycia danego dnia. Rano pociąg może rozpocząć swoją trasę przy dowolnym urządzeniu. Tor pomiędzy dwoma bezpośrednio sąsiadującymi maszynami, kolejka pokonuje w czasie jednej sekundy. Pociąg nie może się zatrzymać na torze pomiędzy urządzeniami. Od maszyny znajdującej się na i-tym miejscu w j-tym rzędzie pociąg może przejechać do urządzeń znajdujących się na pozycjach:

• i-1,j
• i+1,j
• i,j-1
• i,j+1

Kolejka może również pozostać przez dowolną liczbę sekund przy obecnej maszynie. Niestety urządzenia zamontowane przez Jana są, delikatnie mówiąc, mało wydajne. W ciągu jednej sekundy z kranu maszyny wypływa co najwyżej jedna kropla. Na dodatek z kurka może lecieć zarówno woda źródlana jak i mineralna, przy czym z racji poprzedniego ograniczenia nigdy nie nastąpi to w tej samej sekundzie.

Jan zauważył, że każdego dnia wydobycie przebiega tak samo. W związku z powyższym zapisał on, z którego kranu i o jakiej porze wypływa kropla wody. Zna on również jej rodzaj. Nasz bohater zdecydował, że będzie zbierał wodę tylko jednego typu, źródlaną albo mineralną. Teraz musi dokonać wyboru, którą będzie wydobywał, zanim jednak to zrobi Jan chce wiedzieć ile maksymalnie kropel wody każdego rodzaju może zebrać w ciągu dnia?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1;270000] oznaczająca liczbę kropel jakie wypłyną z kranów. W kolejnych n liniach znajdują się opisy kropel.

Każdy opis składa się z trzech liczb t ∈ [1;100], x ∈ [0;100], y ∈ [0;100] i jednej z liter z albo m. Liczba t oznacza czas kiedy wypłynie kropla, podany w sekundach. Liczby x, y określają współrzędne urządzenia, z którego wypłynie. Litera z oznacza, że będzie to woda źródlana, zaś m mineralna.

Wyjście

Na wyjściu należy wypisać dwie liczby oddzielone spacją: maksymalną liczbę kropel wody źródlanej jaką Jan może zebrać w ciągu całego dnia oraz maksymalną liczbę kropel wody mineralnej.

Przykład

Wejście

8
1 0 0 z
2 0 0 m
3 0 0 z
1 0 1 m
2 0 1 m
98 0 2 z
99 0 2 z
100 0 2 m

Wyjście

4 3