Postar

Ο Mirko έχει δουλειά ταχυδρόμου σε μια μικρή πόλη στους λόφους. Η πόλη μπορεί να αναπαρασταθεί με έναν πίνακα ~N \times N~. Κάθε πεδίο περιέχει ένα από τα ακόλουθα, αποκλειστικά: ένα σπίτι που συμβολίζεται με "K", το ταχυδρομείο που συμβολίζεται με "P" ή ένα βοσκότοπο που συμβολίζεται με ".". Επιπλέον, σε κάθε πεδίο εκχωρείται ένα υψόμετρο.

Κάθε πρωί, ο Mirko παραδίδει αλληλογραφία σε όλα τα σπίτια της πόλης. Ξεκινά από το πεδίο που συμβολίζεται με το "P", το οποίο αντιπροσωπεύει ένα ενιαίο ταχυδρομείο στην πόλη. Ο Mirko επιτρέπεται να κινείται οριζόντια, κάθετα και διαγώνια, μόνο σε παρακείμενα τετράγωνα. Μόλις παραδώσει το τελευταίο ταχυδρομείο, πρέπει να επιστρέψει στο ταχυδρομείο.

Ο Mirko δεν είχε ιδέα για το πόσο κουραστική θα είναι η δουλειά του. Αφήστε τη διαφορά μεταξύ των υψών του υψηλότερου και του χαμηλότερου πεδίου που επισκέπτεται ο Mirko κατά την παράδοση της αλληλογραφίας να είναι ίση με την κούρασή του. Βοηθήστε τον και προσδιορίστε τη λιγότερη δυνατή κούραση για τον Mirko για να παραδώσει όλη την αλληλογραφία.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο ~N\;(2 \leq N \leq 50)~.

Οι ακόλουθες ~N~ γραμμές αντιπροσωπεύουν πεδία στην αντίστοιχη γραμμή πίνακα. Ο χαρακτήρας "P" θα εμφανίζεται ακριβώς μία φορά, ενώ ο χαρακτήρας "K" θα εμφανίζεται τουλάχιστον μία φορά.

Έξοδος

Οι ακόλουθες ~N~ γραμμές περιέχουν η καθεμία ~N~ θετικούς ακέραιους αριθμούς, τα ύψη των πεδίων στην αντίστοιχη γραμμή πίνακα. Αυτές οι τιμές είναι μικρότερες από ~1\,000\,000~.

Βαθμολογία

Σε μια γραμμή τυπώστε έναν μόνο ακέραιο που αντιπροσωπεύει την ελάχιστη δυνατή κόπωση.

Παραδείγματα

input

2
P.
.K
2 1
3 2

output

0

Επεξήγηση του 1ου παραδείγματος:

Ξεκινώντας από το ταχυδρομείο, ο Mirko μπορεί να μεταφερθεί απευθείας στο χωράφι με το σπίτι, να παραδώσει την αλληλογραφία και να επιστρέψει πίσω στο ταχυδρομείο. Εφόσον και το χωράφι με το ταχυδρομείο και αυτό με το σπίτι έχουν το ίδιο υψόμετρο, η κούραση του Mirko ισούται με μηδέν.

input

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

output

2

input

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

output

5