Bakterije

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

Κάθε βακτήριο ξεκινά την περιπέτειά του σε ένα συγκεκριμένο κελί, κοιτάζοντας ένα από τα τέσσερα γειτονικά κελιά και εκτελεί τις ακόλουθες ενέργειες κάθε δευτερόλεπτο:

1. Διαβάζει τον αριθμό ~X~ που ανήκει στο βακτήριο στο τρέχον κελί.
2. Περιστρέφεται κατά 90 μοίρες δεξιόστροφα, ~X~ φορές.
3. Αν είναι στραμμένο προς ένα κελί έξω από τον πίνακα, γυρίζει 180 μοίρες.
4. Τέλος, μετακινείται στο κελί που βλέπει.

Ο Luka έχει τοποθετήσει μια παγίδα σε ένα κελί. Η παγίδα θα ενεργοποιήσει και θα σκοτώσει τα βακτήρια μόλις πατήσουν όλα σε αυτό το κελί στο ίδιο δευτερόλεπτο. Επειδή ο Luka έχει μόνο δύο ώρες μάθημα χημείας σήμερα, βοηθήστε τον να καθορίσει πόσο θα διαρκέσει το παιχνίδι, σε δευτερόλεπτα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους θετικούς ακέραιους ~N~ ~(3 \le N \le 50)~, ~M~ ~(3 \le M \le 50)~ και ~K~ ~(1 \le K \le 5)~.
Η δεύτερη γραμμή εισόδου περιέχει τους θετικούς ακέραιους ~X~ και ~Y~, τη γραμμή και τη στήλη όπου ο Luka έχει τοποθετήσει την παγίδα.
Το υπόλοιπο της εισόδου αποτελείται από περιγραφές βακτηρίων, για κάθε βακτήριο ~i~ από 1 έως ~K~:

• δύο θετικοί ακέραιοι ~X_i~, ~Y_i~ - η σειρά και η στήλη του αρχικού κελιού του βακτηρίου ~i~ και ο χαρακτήρας ~C_i~ που αντιπροσωπεύει την αρχική κατεύθυνση που βλέπει το βακτήριο (U - επάνω, R - δεξιά, D - κάτω, L - αριστερά) .
• Πίνακας ~N \times M~ ψηφίων από 0 έως και 9. το ψηφίο στη σειρά ~x~ και στη στήλη ~y~ αντιπροσωπεύει τον αριθμό στο κελί ~(x,\;y)~ που ανήκει στο βακτήριο ~i~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τη συνολική διάρκεια του παιχνιδιού του Luka, σε δευτερόλεπτα. Εάν το παιχνίδι δεν τελειώσει ποτέ, τυπώστε -1.

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

input

3 3 1
2 2
1 1 R
010
000
000

output

3

input

3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301

output

8ιν

input

4 4 3
4 3
1 1 U
1001
0240
3322
2327
1 3 L
9521
2390
3020
2421
2 2 D
3397
2013
1102
7302

output

296