Ślimaki

Limit pamięci: 128MB

Wasza oślizgłość, natrafiliśmy na wielki problem logistyczny podczas badań na planecie Hexagonia. Znajdują się tam istoty poruszające się na DWÓCH, a nie jednej nodze i nie wydzielających śluzu! W dodatku potrafią się poruszać po terenie nieradioaktywnym, co rokuje wielkie nadzieje dla przyszłego rozwoju naszej nauki. Na terenie o rozmiarze N na M podzielonym na sześciokąty foremne potrzebujemy wybudować połączenie północy z południem, żeby mieć dokładny wgląd w ich bardziej intymne i pożyteczne edukacyjnie rejony. Wszystkie sześciokąty mają jedną z głównych przekątnych ustawioną równolegle do południków. Część pól jest zamieszkała przez niezbadany gatunek, część to pola naturalnie promieniotwórcze a reszta jest niezamieszkała. Niestety ponieważ nasz naród ślimaków jest ograniczony fizycznie, musimy zrzucić bomby atomowe, żeby stworzyć bardziej przyjazne dla nas środowisko, które umożliwi poruszanie się. Rzecz jasna, nie chcemy zbyt ingerować w ich ekosystem (a tak na prawdę, to z kwestii ekonomicznych), więc potrzebujemy abyś napisał program do wyznaczenia minimalnej liczby bomb atomowych do wyprodukowania w naszych manufakturach.

Wejście

Na wejściu podane są trzy liczby: N - liczba "kolumn" i M - liczba wierszy oraz C - liczba pól specjalnych (zamieszkałych lub naturalnie radioaktywnych), gdzie 1 ≤ N,M ≤ 1000 i 0 ≤ C ≤ M*N. Następnie w C kolejnych liniach dane są dwie liczby i litera: x, y, k (1 ≤ x ≤ N, 1 ≤ y ≤ M, k ∈ {"o","x"}), które kolejno oznaczają: współrzędne pola i typ danego pola: litera "x" oznacza pole zamieszkałe, a litera "o" oznacza pole naturalnie promieniotwórcze.

Wyjście

Wypisz jedną liczbę oznaczającą minimalną liczbę bomb, które trzeba zrzucić. Jeśli mimo zrzucania bomb nie będzie się dało połączyć północy z południem, należy wypisać -1.

Przykład

Dla danych wejściowych:

5 4 11
1 3 o
2 3 x
4 1 x
1 1 o
2 2 x
4 3 o
3 4 x
1 2 x
5 2 o
4 4 x
5 4 x

poprawną odpowiedzią jest:

3