Strelice

Ο Hansel και η Gretel παίζουν ένα πολύ γνωστό παιχνίδι, τα "Βέλη", που διεξάγεται σε έναν πίνακα με γραμμές ~R~ και στήλες ~S~. Σε κάθε κελί υπάρχει ακριβώς ένα βέλος που δείχνει σε μία από τις τέσσερις κύριες κατευθύνσεις.

Ο Hansel παίζει πρώτος και η κίνησή του είναι να χρωματίσει ακριβώς ~K~ κελιά στον πίνακα που δεν βρίσκονται στην τελευταία στήλη. Στη συνέχεια, η Gretel τοποθετεί ένα ρομπότ σε ένα αυθαίρετο κελί στην πρώτη στήλη. Τώρα το ρομπότ μπορεί να κινηθεί μόνο του, μετακινώντας από το τρέχον κελί στο κελί που δείχνει το βέλος. Αν κάποια στιγμή το ρομπότ βρίσκεται στην τελευταία στήλη, σταματά και το παιχνίδι τελειώνει.

Ο νικητής του παιχνιδιού καθορίζεται με τον εξής τρόπο:

• Εάν το ρομπότ σταμάτησε και το παιχνίδι τελείωσε, ο Hansel είναι ο νικητής εάν το ρομπότ πέρασε ακριβώς από ένα χρωματιστό κελί και η Gretel είναι ο νικητής εάν το ρομπότ πέρασε από μηδέν ή περισσότερα από ένα χρωματιστά κελιά.
• Εάν το ρομπότ δεν σταμάτησε μετά από ένα πεπερασμένο χρονικό διάστημα (με άλλα λόγια, εάν το ρομπότ έχει κολλήσει σε έναν άπειρο βρόχο), ο Hansel είναι ο νικητής.

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

Προσδιορίστε εάν ο Hansel μπορεί να εξασφαλίσει τη νίκη του ανεξάρτητα από το πού τοποθετεί αρχικά η Gretel το ρομπότ. Εάν η απάντηση είναι θετική, βγάζετε \(Κ\) κελιά που μπορεί να χρωματίσει για να κερδίσει.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους ~R,\;S,\;K\;(1 \le R \times S \le 1\,000\,000,\;1 \le K \le 50)~.
Κάθε μία από τις ακόλουθες ~R~ γραμμές περιέχει ~S~ χαρακτήρες 'L', 'R', 'U' ή 'D' που δηλώνουν την κατεύθυνση του βέλους στο αντίστοιχο κελί του πίνακα (L - αριστερά, R - δεξιά, U - επάνω , D - κάτω).

Έξοδος

Εάν ο Hansel δεν μπορεί να εξασφαλίσει τη νίκη του, η έξοδος είναι -1.
Εάν ο Hansel μπορεί να εξασφαλίσει τη νίκη του, τυπώστε ~K~ γραμμές . Σε κάθε γραμμή, τυπώστε τους αριθμούς ~A~ και ~B~ διαχωρισμένους με κενό ~(1 \le A \le R,\;1 \le B \le S)~, που δηλώνουν τη γραμμή και τη στήλη του κελιού που πρέπει να χρωματίσει ο Hansel. Όλα τα χρωματιστά κελιά πρέπει να είναι διαφορετικά.
Εάν υπάρχουν πολλές λύσεις, τυπώστε οποιαδήποτε.

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

input

4 3 1
DRD
DUD
DUD
RUL

output

4 2

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

Εάν ο Hansel χρωματίσει το κελί ~(4,\;2)~, το ρομπότ θα περάσει από αυτό ανεξάρτητα από το πού το τοποθετήσει αρχικά η Gretel, οπότε ο Hansel θα είναι ο νικητής.

input

3 3 2
RRR
RRR
RRR

output

-1

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

Εφόσον ο Hansel πρέπει να χρωματίσει ακριβώς 2 κελιά, αυτό σημαίνει ότι τουλάχιστον μία από τις τρεις σειρές δεν θα περιέχει έγχρωμο κελί. Η Gretel μπορεί να τοποθετήσει το ρομπότ σε αυτή τη σειρά και θα περάσει από 0 χρωματιστά κελιά, οπότε η Gretel θα κερδίσει.

input

4 4 2
RRDL
RRDL
DLRD
RRRL

output

2 3
4 1

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

Συμβουλευτείτε την εικόνα από την περιγραφή εργασίας.